Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

코포 후기를 쉰지 좀 되었는데, 억울하고 부끄러운 마음에 더 정진하고자 이제부터라도 후기를 적으려 합니다.

 

ㅋㅋ

 

A. Diverse Game (0:02, +)

배열을 밀면 된다. \(N=1\)이나 \(M=1\)인 경우만 유의해주자.

 

B. Fun Game (0:10, +)

s를 조작했을 때, 가장 처음에 등장하는 1 뒤로는 자유롭게 바꾸어줄 수 있다. 따라서 두 문자열에서 가장 먼저 등장하는 1의 위치를 구한 뒤 비교해주자. 역시 0으로만 이루어진 경우 등에 유의하자.

 

C. Hungry Games (0:16, +)

조건을 만족하지 않는 구간의 수를 구해 보자. 이분 탐색 또는 투 포인터를 이용해 각 시작 위치에 대해 \(X\)를 처음 넘기는 지점을 구한 후, 이를 적절히 합치면 된다.

 

D. Funny Game (0:27, +)

연산을 거꾸로 적용해보자. 수는 \(N\)개인데 mod는 \(N-1\)이므로 비둘기집의 원리에 의해 최소 한 쌍은 묶어줄 수 있고, 이를 귀납적으로 적용하면 된다. 스몰 투 라지를 짜느라 좀 걸렸다.

 

E. Wooden Game (0:43, +)

\(a | b \leq a + b\)이다. 따라서 트리가 하나라면 자르지 않는 것이 가장 좋다. 우선 \(N\)이 가장 큰 트리를 고른 후, 남은 트리들은 빈 비트를 채우는 데에 사용해주자. 큰 비트부터 보며 채울 수 있다면 그 비트를 그대로 사용하고, 중복이 등장하면 1을 011...111로 만들어 아래 비트를 모두 채워 주면 된다.

 

F. Stardew Valley (upsolved)

0인 간선이 없다면 euler circuit 문제이다. 우리의 목표는 1인 간선만으로 이루어진 그래프에 0인 간선을 적절히 추가해 모든 정점의 차수를 짝수로 만드는 것이다. 1인 간선으로 만든 그래프가 connected이기 때문에 생각하기가 쉬웠다. 0인 간선들로만 이루어진 component를 살펴 보자. 만약 어떤 component에 홀수 정점이 홀수 개 있다면 construction이 불가능하며, 짝수 개 있다면 정점을 아무렇게나 짝지은 뒤 DFS tree 위에서의 경로를 symmetric difference 해 켜진 간선만 사용하면 된다. 이는 dfs를 잘 사용하거나 tree dp를 쓰면 된다. 이후는 그냥 오일러 경로를 찾으면 끝난다.

 

풀이를 빨리 찾아서 기분이 좋아 빠르게 짜려 했지만, 문제는 짜 둔 오일러 투어 구현체가 없었다는 점이다. 다행히 빠르게 인터넷에서 복사를 해 왔는데 어째서인지 2번 테케에서 계속 틀려서 멘탈이 나갔다. 그렇게 1시간을 복붙 탓만 하며 뇌절하다가 대회가 끝났다. 오늘 보니 역시나 가져온 구현체 문제가 아니라 그냥 내가 초기화를 이상하게 한 탓이었다. 첫 제출 코드에서 1줄 추가해서 맞았다. 레드 퍼포와 IM을 대가로 배웠다고 생각하고 싶지만 버린 것이 너무 크다.. 정말 안타깝다.