Codeforces Hello 2026 후기

몇달간 1600대 초반에만 머무르던 나를 바로 1700대 중반으로 보내준 Hello 2026에 대한 후기를 작성하겠다.

:blobaww:

 

A. Binary Array Game (00:00 ~ 00:05)  

문제를 잘 관찰해보면, Alice가 이기기 위해서는 초기 배열에 0이 없거나, 한번의 시행 뒤에 배열에 0이 없어야 한다. 이를 위해서는 초기 배열에서 A[0] 혹은 A[-1] 값이 1이면 된다는 사실을 알 수 있다.

 

B. Yet Another MEX Problem (00:05 ~ 00:14)

문제가 좀 복잡한데, 어떤 길이 K의 버킷을 잡아 하나를 제거한다 해도, K-1개로 이루는 mex 값은 항상 유지시킬 수 있다는 사실을 통해 수열 자체의 mex 값과 K 중 최솟값을 출력하면 된다.

 

C. War Strategy (00:14 ~ 00:56)

솔직히 좀 어려웠다. 일단 식 정리하기도 쉽지 않았고, 최적의 메커니즘을 설계하는 것도 만만치 않았다. 차분히 정리해보니 양옆으로 차지할 개수를 정해놓으면 $O(1)$에 최소 시간을 구할 수 있단걸 알게 되었고, 굳이 이탐을 쓸 필요는 없어보여서 $O(N)$에 해결했다.

 

D1. Tree Coloring (Easy Version) (00:56 ~ 01:18)

조금의 관찰을 통해, 같은 깊이인 노드의 개수들 중 최댓값과 각 노드의 (자식의 개수)+1 중 최댓값 중의 최댓값을 구하면 된다는 것을 알게 되었다. 자세한 건 후술하겠다.

 

E. LCM is Legendary Counting Master (01:18 ~ 02:01)

D1을 풀고 솔브수를 보니 E가 D2보다 조금 더 솔브수가 많은 걸 확인했다. 그래서 바로 D2를 버리고 E로 튀었다!

식이 꽤나 복잡해보이는데, $\frac{1}{lcm(a,b)} = \frac{gcd(a,b)}{ab} \le \frac{|a-b|}{ab} = |\frac{1}{a} - \frac{1}{b}|$ 을 이용해 잘 정리하면 다음의 결과를 도출할 수 있다.

$$ a_1 = 1 $$

$$ gcd(a_i, a_{i+1}) = a_{i+1} - a_{i} \ (1 \le i \le N-1) $$

이를 이용해 간단한 dp를 짜주면 $O(NM \ln{M})$ 에 문제를 해결할 수 있다.

 

D2. Tree Coloring (Hard Version) (02:01 ~ 02:53)

내가 가장 극적으로 푼 문제이자, 오렌지 퍼포에 가장 큰 기여를 한 문제이다!

E를 풀고나니 1시간 가량이 남아서, 남은 시간을 모두 D2에 박기로 결심했다. 여러가지 시도를 해봤지만 결국 bfs 처럼 각 depth별로 쪼개면서 구해야겠다고 생각했다. 그러자 든 생각은, 각 노드가 속해야 하는 집합의 번호 (color)를 한 층씩 구하다 보면, 각 노드가 부모와 color이 같은지 여부만 잘 확인해주면 될 것 같았다.

앞으로 자식의 color과 부모의 color 이 같아지는 상황을 '충돌'이라고 하자. 난 이 충돌의 수를 최소화하고 싶었고, 그 횟수는 최대 한 번임을 알게되었다. 구성하는 방법은 다음과 같다.

먼저, 깊이가 $d$인 노드들을 color이 높은 순으로 정렬한다. 그리고 깊이가 $d$인 노드들의 자식 ($d+1$)의 color을 1부터 증가시키며 매기다 보면 $d$의 color은 감소, $d+1$의 color은 증가하기 때문에 최대 한번 충돌한다. 일단은 충돌을 피해야 하기 때문에, 충돌 시 자식의 color을 1 증가시켜 매긴다. 그러면, $d+1$의 color 중 최댓값은 ($d+1$의 원소 개수) + 1 이 될 것이고, 이는 운이 안 좋으면 D1에서 구한 max 값을 넘길 수 있다!

하지만, 동시에 이런 관찰을 할 수 있다. $d+1$의 color 중 최댓값이 max 값을 넘긴다면, $d$의 원소는 하나가 아닐 것이다. 만일 $d$의 원소가 하나라면, D1에서 구한 max 값은 ($d+1$의 원소 개수) + 1 이 될 것이고, 이는 max 값 이하이므로 모순이다. 즉, 충돌이 발생하는 원소와 부모가 다른 다른 원소가 $d+1$에 존재한다는 것이고, 그 원소와 color을 swap 한다면 아무런 충돌도 발생하지 않음을 알 수 있다.

 

오렌지 퍼포!!!

 

처음으로 오렌지 퍼포를 띄우고 Div.1+2 에서 6솔을 해서 기분이 좋다 ㅎㅎ Div. 3에서도 6솔은 안 해봤는데 1+2에서 먼저 해서 기분이 이상하다. 이 기세를 이어서 Road to Purple 을 이어나가야겠다.