CodeForces Round 1007 - Div 2

https://codeforces.com/contest/2071

 

 

Performance Rating : 2300

 

A

예제를 보고 규칙성을 못 찾아서 문제를 읽어보니 세 명이라길래 3으로 나눈 나머지를 봤더니 1인 경우 YES, 0, 2인 경우 NO였다.

 

B

처음에는 2 1 3 4 ... 이렇게 출력해 주면 끝나는 문제인 줄 알고 제출했다가 틀렸다. $n(n+1)/2=k^2$인 $n$이 1밖에 없는 줄 알았는데 더 있는 것을 확인하고 $n(n+1)/2=k^2$인 $n$에서는 -1을 출력하고 아니라면 $n$이하이면서 $i(i+1)/2=k^2$인 $i$에 대해 1과 2를 swap 했듯이 $i$와 $i+1$을 swap해주는 방식으로 출력했다.

 

C

st, en에 관계없이 어떤 규칙을 가지고 움직여야 될 것 같다는 느낌이 강하게 들었다. st, en의 위치와 거리에 영향을 받는다면 풀 수 없는 문제가 될 것 같았기 때문이다. 그래서 en을 루트로 했을 때 st에서 en으로 가는 경로 순서대로 subtree를 모두 처리해 주는 방식을 생각해 보았다. 여러 케이스에서 실험을 해본 결과 특정 subtree의 루트에서 탐색을 시작하고 dfs 방문 순서의 반대로 정점을 선택하면 루트로 돌아오는 것을 확인했다. 그래서 dfs를 한번 돌려 en에서 st로 가는 루트를 찾아놓고 dfs 방문 시 st로 가는 경로를 가장 먼저 찾도록 트리 구조를 바꿔주고 dfs를 한번 더 돌러 해결했다. 엄밀한 증명보다는 proof by AC로 풀었다.

 

D1

처음에는 대략 60개의 누적합을 만들어놓으면 풀리는 문제라고 착각을 해서 구현을 했다가 예제에서 안 나오는 것을 보고 다른 풀이를 생각하기 시작했다. 여기서 $2k> n$에 대해 $a_{2k}=a_{2k+1}$이므로 $a_{2k}^a{2k+1}=0$이라는 사실을 활용하면 재귀적 구현이 되겠다는 생각을 했다. 변수를 없애기 위해 $a_{2n+1}$까지 구해놓고 재귀 코드를 구현해 풀었다.

 

E

D1을 푼 시점에서 E의 솔브수가 더 많기도 했고 문제를 보고 리루팅 풀이가 떠올라 풀기 시작했다. tree dp로 각 subtree에서 리프의 기댓값을 구해놓고 리루팅으로 문제를 풀 생각을 했다. 10분을 남겨놓고 코드를 완성했는데 틀렸다. 리루팅 풀이로 구현을 다시 해서 맞았다. 식이 복잡해 인덱스 실수를 한 것으로 보인다.