Codeforces Round 1001 후기

나는 누구? "Codeforces International Master 오너"

어제 코포에서 퍼포 2600을 내고 IM을 달았다.

 

0:00

A번을 잡았다.

풀이

어떤 방식으로 flip을 하더라도 1의 개수를 최대 1개 줄일 수 있고, 1 1개를 고르면 실행할 수 있다. 입력받은 문자열에서 1의 개수를 세서 출력한다.

1분만에 AC를 받았다.

0:01

B번을 잡았다.

발상은 바로 됐는데, 구현을 실수해서 1틀했다.

풀이

1번과 n번 시계를 커버하기 위해서는 1번 -> n번 -> 1번 -> n번 -> ... 순으로 움직여야 한다. 이 움직임을 택했을 때 각 시계에 대해서 현재 방문부터 다음 방문까지 간격의 최댓값을 구하자. n이 5이면 8 6 4 6 8 로 나올 것이다. 이 배열을 b라고 하자.

a[i] <= b[i]인 i가 있으면 no, 아니면 yes

원래 징크스를 잘 안 믿는데, 항상 B에서 1틀 이상 하는 징크스가 있는 것 같다. 그렇게 어려운 문제도 아닌데 희한하게 어디선가 실수가 생긴다.

0:07

C번을 잡았다.

발상하는 데 5분정도 걸렸는데 구현은 쉬워서 14분에 AC를 받았다.

처음에 예제 입출력을 보고 내가 예상한 범위와 전혀 다른 출력이 있어서 당황했는데, 일단 문제에서 제시한 연산을 적용하다 보니까 풀이가 나왔다.

풀이

Reverse 연산(1번 연산)은 Difference sequence로 replace하는 연산(2번 연산)에서 각 원소의 부호를 바꿔주는 역할을 한다. 즉 1번 연산을 어떻게 하더라도 2번 연산을 수행하고 난 뒤 원소들의 총합의 절댓값은 일정하다.

2번 연산을 0번, 1번, ..., n-1번 수행하고 나서 원소들의 총합의 절댓값을 각각 구한다. (0번 수행했을 때에는 절댓값이 아니라 그냥 총합을 구해야 할 것이다.) 그리고 그 중에 최댓값이 답이다.

0:14

D의 배점이 E1의 배점보다 커서 둘 중 어떤 것이 더 쉬운지 알 수 없다. 일단 두 문제를 다 읽어봤고, E1이 D보단 덜 막막하다는 느낌이 들었다. 슥보를 보니까 0:20쯤에 E1 퍼솔이 D 퍼솔보다 먼저 나와서 E1을 잡았다. 풀이는 바로 나왔는데 B번과 마찬가지로 구현에서 실수 하나 있어서 1틀했다.

풀이

value가 n인 노드를 선택하면 필패이다.

따라서 value가 n-1인 노드에 대해서 그 노드의 서브트리 밖에 value가 n인 노드가 있으면 그 노드를 골랐을 때 필승이다.

위 조건을 만족하는 노드가 없다면, value가 n-1인 노드를 선택하면 필패이다.

그러면 value가 n-2인 노드들에 대해 위 작업을 수행한다.

 

트리에 오일러 경로 테크닉을 박으면 어떤 노드의 서브트리를 하나의 구간으로 치환할 수 있다.

value가 n인 노드들을 세그에 업데이트하고, value가 n-1인 노드 v에 대해서 [1, n] 구간과 v의 서브트리에 해당하는 구간에서 업데이트 된 노드들의 수가 같은지 판단한다. 다르다면 v를 선택했을 때 필승이므로 v를 출력하고 return한다.

이어서 value가 n-1인 노드들을 세그에 업데이트하고, value가 n-2인 노드들에 대해서 위 작업을 수행한다.

이를 value가 1인 노드들까지 반복하고, 아직도 return하지 않았다면 필승전략이 없는 것이므로 0을 출력한다.

 

세그에 업데이트 할때 in[k]번 인덱스에 업데이트해야 되는데 k번 인덱스에 업데이트해서 1틀했다.

0:32

D를 잡고 풀었다. 발상하는데 20분정도 걸렸다.

풀이

u를 root로 보고 v의 subtree에 +1 해주는 연산을 (u,v)라 하자.

어떤 노드 v에 대해서 v의 subtree가 balanced라면 이 subtree를 노드 v 하나로 치환할 수 있다.

부모 노드 u와 자식 노드 v에 대해서 u의 value가 v의 value 이상이라면 문제가 없다. (1, v)를 충분히 많이 해주면 된다. 이 경우를 type 1이라 하자.

아니라면 (v, u)를 충분히 많이 시행하면서 value를 맞춰준다. 이 때, v의 subtree가 아닌 모든 노드의 value가 1씩 증가하므로 이를 기록해야 한다. 이 경우를 type 2라 하자.

 

트리에 DFS를 돌리는데, dfs(k)는 {k를 루트로 하는 서브트리의 value, type 2 연산의 횟수}를 리턴할 것이다. k의 자식 노드들에 대해서 dfs를 돌리고, type 2의 횟수만큼 k의 value가 증가한다. 총 증가한 양을 e라고 하자. 자식 노드 v의 value는 dfs(v).first + e - dfs(v).second일 것이다.

e + r[k] < (v의 value)인 경우에만 k의 초기 value를 r[k]로 한 뒤 type 2를 시행하면 되고, 아닌 경우는 k의 초기 value를 적당히 설정해서 type 2를 추가로 실행하지 않아도 되도록 하자. (v의 value) < e + l[k]인 경우에는 type 1을 시행해서 v의 value를 올려줄 수 있고, v의 value가 e+l[k], e+r[k] 사이라면 (v의 value) - e를 k의 초기 value로 설정한다. 여기까지 모두 선형에 가능하므로 전체 시간복잡도는 O(N)이다.

 

풀이 정리하는데 상당히 복잡해서 에디토리얼 까봤는데 조금 더 고능한 발상을 해서 훨씬 간단하게 푼 것 같다.

1:04

일단 A ~ E1까지 모두 풀고 슥보를 확인해 보니까 90등대였고 E2와 F는 3~4명 정도가 풀었다.

F의 솔브 수가 더 많아서 F를 잡았는데 아무런 유의미한 발상을 못하겠어서 E2를 잡았다.

E2에서는 "각 노드를 선택했을 때 상대가 필패인지 판정하자"라는 관찰과 "첫 수 이후 남아있는 노드 v의 서브트리 안의 u에 대해 (노드 v의 value) > (노드 u의 value)이면 뭔가 후공이 이길 것이다"라는 추측을 했다. 더 이상 진전이 없어서 1:30쯤에 포기하고 자러 갔다. 에디토리얼을 까 보니까 내 추측에서 조금 더 발상하면 풀이를 낼 수 있었던 것 같다.

2:30(끝)

ABC는 자명했고, D는 체감상 플레5~4, E1은 플레3~2정도 돼 보였다. E2 풀이를 까보니까 다이아는 아닌 것 같은데, 계속 잡았으면 풀었거나 유의미한 관찰을 할 수 있었을 것 같았다. 빨리 포기해버린게 살짝 아쉽다. 딴거 하다가 끝나고 등수만 봤는데 180등대여서 +50~70정도 하고 2250 근처가 되지 않을까 싶었다. 근데 오늘 일어나서 확인해 보니까 +116을 받고 2300을 찍었다. Happy

이번엔 운이 좋아서 플레 중반까지 풀고 퍼포 2600을 받았지만, 플레 중반까지를 운이 좋아서가 아니라 안정적으로 풀수 있도록 연습이 많이 필요할 것 같다. 설 연휴때 시간 많을거니까 그때 플랜디 열심히 해야겠다. 그리고 오늘 E2랑 F는 언젠간 업솔빙 할거다.