Codeforces Round 1020 (Div.3) 버추얼 후기
시작하며…
코포 라운드 1020 디비전 3을 버추얼로 치게 되었는데, 원래는 본 대회에 나갈 생각이었지만 대회 당일에 헌혈 부작용으로 실신하는 바람에… 부작용 당첨률이 0.1%라는데 저어어엉말 운 좋게 당첨되었다. 나름 헌혈 5회차 베테랑인데 이런 경우는 처음이라 매우 당황스러웠다… 그냥 휴식을 취하고 아쉽지만 버추얼로 참가했다.
그런데 생각보다 퍼포먼스가 나쁘지 않아서 (일단 지금보다 점수는 오름) 그냥 참여할걸 그랬다. 어쨌든 시작.
A - Dr. TC
별거 없는 A스러운 문제인데 문제는 내가 이진 문자열을 int로 받아버리는 바람에 두 번이나 페널티를 받았다;;
근데 왜 int로 해도 예제는 다 맞는거냐고
import sys
input = sys.stdin.readline
T = int(input().strip())
for _ in range(T):
n = int(input().strip())
s = input().strip()
one = 0
for i in range(n):
if s[i] == '1':
one += 1
print(one*(n-1)+n-one)
B - St. Chroma
이것도 아주 B번스러운 문제였다. 요즘 MEX 함수를 자주 보는 것 같아서 반가웠다.
풀이는 그냥 x가 나올 때까지 오름차순으로 출력하고, x~n-1까지는 내림차순으로 출력하면 된다. 이때 구현하면서 x가 n-1보다 큰 경우를 주의하자.
import sys
input = sys.stdin.readline
T = int(input().strip())
for _ in range(T):
n, x = map(int, input().split())
if n-1 >= x:
print(*range(x), *range(n-1, x-1, -1))
else:
print(*range(n))
C - Cherry Bomb
a[i]+b[i]의 값을 모든 i에 대해 똑같은 x값으로 맞추면 되는 문제
k를 이용해 가능한 x값의 범위를 구하면 된다. b에 -1만 있는 경우와 하나라도 값이 남아있는 경우를 나눠서 생각하자. 처음부터 입력이 적절하지 않아서 0이 나올 수도 있는 점을 주의.
import sys
input = sys.stdin.readline
T = int(input().strip())
for _ in range(T):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = -1
v = 1
for i in range(n):
if b[i] != -1:
if c == -1 or c == a[i] + b[i]:
c = a[i] + b[i]
else:
v = 0
lo, hi = max(a), min(a)+k
if lo > hi or not v:
print(0)
elif c == -1:
print(hi-lo+1)
else:
print(1 if lo <= c <= hi else 0)
D - Flower Boy
풀다가 환장할 뻔 했던 문제
결국 4번 틀리고 E부터 풀었는데, 틀린 이유가 아주 가관이다.
n == 1일 때 예외처리를 하면서 a[0]보다 b[0]이 크면 b[0]을 출력했어야 하는데 1을 출력하고 있었다. 심지어는 이걸 대회 끝나고 알았다. 그리디 접근이 틀린걸까봐 4틀부터는 패스했는데 이런 이유였을 줄이야;;;
이걸 맞추고 갔으면 6솔로 1800+ 퍼포를 찍을 수 있었는데… 버추얼이라 참 다행이다. 실전이었으면 또 화병으로 실신했을지도 모른다;;
import sys
input = sys.stdin.readline
T = int(input().strip())
for _ in range(T):
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp_front = [0]*n
dp_back = [0]*n
s = 0
for i in range(n):
if s < m and a[i] >= b[s]:
s += 1
dp_front[i] = s
s = 0
idx = m-1
for i in range(n-1, -1, -1):
if s < m and a[i] >= b[idx]:
s += 1
idx -= 1
dp_back[i] = s
if n == 1:
if a[0] >= b[0]:
print(0)
else:
print(b[0]) # 대체 왜 여기서 1을 출력한 거냐고...
continue
r = 10**9 + 7
for i in range(n-1):
if dp_front[i]+dp_back[i+1] == m-1:
r = min(r, b[dp_front[i]])
elif dp_front[i]+dp_back[i+1] >= m:
r = 0
break
if dp_back[0] == m-1:
r = min(r, b[0])
if dp_front[n-1] == m-1:
r = min(r, b[m-1])
if dp_back[0] >= m or dp_front[n-1] >= m:
r = 0
if r == 10**9 + 7:
print(-1)
else:
print(r)
E - Wolf
이런 류의 이분탐색 문제는 처음이라 신선했다.
우선 l-r 범위에서 이분탐색으로 k를 찾기 위해서는 k를 찾기 전까지 고른 mid에서의 배열값만 적절하면 된다. 따라서 역배열 inv를 만들어서 쿼리마다 O(1)로 k의 인덱스를 찾은 뒤 이분탐색을 진행하면서 mid가 k의 인덱스보다 작으면 k보다 작은 값으로, k의 인덱스보다 크면 k보다 큰 값으로 교체하면 된다.
여기서 k보다 작아야 하는데 큰 배열값-k보다 커야 하는데 작은 배열값은 각각 짝을 지어 교체해야 최적이다. 그러고 남은 나머지는 배열의 다른 곳에서 아무 값이나 골라 교체하면 된다.
마지막으로 mid로 사용한 값들이 적절한지 검사하면 된다. 예를 들어서 [3, 2, 1] 인데 f(1, 3, 3) 으로 3을 찾을 수는 없다. k보다 큰 값의 수와 k보다 작은 값의 수를 계산해서 mid로 사용한 값들의 개수와 비교하면 된다.
모든 배열의 인덱스가 1부터 시작하는 점을 주의하자.
import sys
input = sys.stdin.readline
T = int(input().strip())
for _ in range(T):
n, q = map(int, input().split())
lst = [0]+list(map(int, input().split()))
rvs = [-1]*(n+1)
for i in range(n+1):
rvs[lst[i]] = i
for _ in range(q):
l, r, k = map(int, input().split())
if rvs[k] > r or rvs[k] < l:
print(-1, end=' ')
else:
lo, hi = 0, 0
lo_c, hi_c = 0, 0
while l <= r:
m = (l+r)//2
if m == rvs[k]:
break
elif m < rvs[k]:
if lst[m] > k:
lo += 1
else:
lo_c += 1
l = m+1
else:
if lst[m] < k:
hi += 1
else:
hi_c += 1
r = m-1
res = min(lo, hi) # lo, hi끼리 swap
k_hi = n-k
k_lo = k-1
if lo+lo_c > k_lo or hi+hi_c > k_hi: # 가능한 경우인지 검사
print(-1, end=' ')
else:
lo, hi = lo-min(lo, hi), hi-min(lo, hi)
print(2*(res+lo+hi), end=' ')
print()
F - Goblin
무난무난한 dp 문제
dfs로 풀 수 있을 것 처럼 생겼지만 문자열의 최대 길이가 n <= 2*10^5 라서 O(n^2)가 되면 망한다. 대신 그래프에서 어떤 열의 경우의 수가 두 가지밖에 없다. s[i]가 0인 경우 i번째 칸만 1, 나머지는 0 / s[i]가 1인 경우 i번째 칸만 지나갈 수 있는 통로 형태가 된다.
따라서 어떤 열 i에서 나누어지는 구역의 수는 s[i]가 0일 때 i 윗칸과 i 아랫칸으로 두 가지밖에 없다. 이를 이용해서 i의 윗칸을 hi, i의 아랫칸을 lo로 지정한 뒤에 s[i]와 s[i+1]이 0-1, 0-1, 1-0, 1-1 네 가지 경우에 따라 다른 점화식으로 dp를 진행하면 된다.
import sys
input = sys.stdin.readline
T = int(input().strip())
for _ in range(T):
n = int(input().strip())
s = input().strip()
res = 0
if s[0] == '0':
hi, lo = 0, n-1
else:
hi, lo = 0, 1
res = max(res, hi, lo)
for i in range(1, n):
if s[i-1] == '0':
if s[i] == '0':
hi, lo = hi+i, lo+n-i-1
else:
hi, lo = 0, lo+1
else:
if s[i] == '0':
hi, lo = lo+i, n-i-1
else:
hi, lo = 0, 1
res = max(res, hi, lo)
print(res)
마침
G부터는 풀지 못했기 때문에 F까지만 포스팅을 하고 마친다. 시간도 늦었고 D때문에 정신적 충격을 받아서 오늘 당장 업솔빙을 하기는 많이 곤란한 면이 있다.
내가 블루 못갈 실력은 아닌 것 같은데 왜 못 가는지 의문이다. 사실 알 것 같다. D번같은 실수를 계속 해서 그렇다… 하지만 실수도 실력이겠지…
끝
Leave a comment