Codeforces Round 959 (Div. 1 + Div. 2) 업솔빙

 

A, B는 대부분 지문 이해하는데 시간을 사용했고, 지문을 이해하자마자, 풀이가 떠올랐다. 1년 전에는, 초반 두 지문 푸는데만 30분가량을 소모했는데, 이젠, 10분 만에 두 문제를 풀정도가 되었다. (군대 가서 아무것도 안 했다.)

 

C는 보자마자, 자료구조가 떠올랐다.

 

$i$ 번째 배열에서 모든 $L \leq i$에 대해, 구간 $[L, i]$ 의 정답을 그때 그때 알아내면 되겠구나라고 생각이 매몰되었고, 그럼 모든 출발지점에서부터 $A[i]$ 값들을 더해주며, $X$를 넘으면, 다 0으로 보내자라고 생각을 했다.

 

내게 가용가능한 스플레이트리 템플릿이 없었기에, rotate() 랑 splay()만 복붙 해서 가져온 다음, 하드코딩을 했다. 당연히 구현이 힘들므로, 50분이나 잡아먹었다.

 

D. Funny Game

전혀 재미있지 않다. 이것은 비둘기집 원리를 이용한 문제이고, 견식을 높이는데 도움이 되었다. 이런 류의 문제는 풀어본 적도 없고 비둘기집 원리도 많이 사용해보질 않아서, 대회에서 풀 때는 " $N \leq 2000$ 을 이용해, 대충 무조건 겹친다. "라고만 생각했고, 이후 아무것도 하지를 못했다.

 

자 문제를 거꾸로 생각해 보자. 우린 오직 하나의 모든 요소가 연결된 컴포넌트에서 시작하는 것이다. 하나를 떼어 낼 때, $N-1$로 나누어 떨어져야 한다.

 

집합에 있는 모든 수를 $mod \; N - 1 $ 처리하면, 집합에 수는 $N$ 개 있기 때문에, 무조건 겹치는 수가 나올 수밖에 없다.

겹치는 그 두 수가, $N-1$번째 연산에서 처리 가능한 쿼리이고, 둘 중 아무나 집합에서 떼어내고 버린다.

 

이 과정을 반복할 수 있다.

$X$ 번째 연산에서는 $X+1$개의 수중에서 $\mod X $ 연산을 하고 겹치는 수를 찾기만 하면 되기 때문에, 무조건 가능하다.

 

E. Wooden Game

이건 보자마자, 그냥 에라 모르겠다 하고, 풀진 않았던 문제이다. 업솔빙을 시작해 보고, 10분도 안 돼서 답을 찾아내긴 했다. 좀 슬프다...

 

일단은 테케가 1이고 트리의 크기가 $N$ 일 때, 정답은 $N$이 된다. $N$보다 큰 수를 만들 수 없기 때문이다.

 

트리의 크기들, $V_1, V_2, V_3, \cdots , V_k$가 주어 질 때, 무슨 조합으로 가장 큰 숫자를 만들 수 있을까?

 

일단, 트리의 크기가 $N$일 때, $N$보다 작은 모든 숫자를 OR 연산을 시킬 수 있다. 리프노드를 하나씩 때다가 한 번에 트리를 없애버리면 $N$보다 작은 숫자를 만들 수 있기 때문이다.

 

만약, 트리를 뭐 어떻게 유용하게 분할해야 해서, 숫자 $\big( A_1, A_2, A_3, \cdots , A_k \big)$로 엄청 유용하게 분할을 한다고 쳐보자.

 

$A_1 \; | \; A_2 \; | \; A_3 \; | \; \cdots \; | \; A_k$ 는 $N$보다 작은 숫자 중 하나이다.

 

이것을.. 비트열이라고 해보자.. 

4번째 비트열이 같다. 그럼 그 뒤쪽 비트열을 다 채우는 것이 가능하다. 더 작은 숫자인 것이 자명하기 때문이다.

이렇게 그리디 하게, 비트가 겹치면, 바로 뒤쪽을 다 채워버리면서 가장 크게 만들 수 있다. 

업솔빙은 다음 콘테스트 전까지 다 하려고 한다.