IOI 2024 Day 1

이집트 알렉산드리아에서 IOI 2024 Day 1 대회가 진행되었다. Day 1 기준 한국 학생들의 성적은 다음과 같다.

• 김은성, 100 / 58.64 / 59, 217.64점, 22등
• 정희우, 100 / 53.89 / 59, 212.89점, 26등
• 정민찬, 100 / 79.64 / 17, 196.64점, 43등
• 우민규, 100 / 31.40 / 59, 190.40점, 52등

올해도 작년과 같이 모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않다. 또한 그 경계선의 점수 차가 크지 않은 편이다. Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 좋은 결과를 내기를 소망한다.

Day 1의 만점자는 중국의 Kangyang Zhou로 대회 시작 3시간 1분만에 모든 문제를 해결했다. Message 문제의 만점을 받는 것이 매우 어렵다고 생각해서, 이번 Day 1의 성취가 아주 대단하다고 생각한다. 그 뒤를 폴란드의 Adam Gąsienica-Samek (291.22), 중국의 Yuchong Guo (287.17) 이 따랐다.

구현한 코드는 https://github.com/koosaga/olympiad/tree/master/IOI 에 모두 올라와 있다.

Day 1 Problems PDF

message-ISC.pdf

0.15MB

message-KOR.pdf

0.37MB

nile-ISC.pdf

0.12MB

nile-KOR.pdf

0.23MB

tree-ISC.pdf

0.18MB

tree-KOR.pdf

0.34MB

Problem 1. 나일강 (nile)

서브태스크 1 (6점)

모든 보트의 $W[i]$ 가 동일하기 때문에, 두 개의 유물이 존재하기만 하면 쿼리로 주어진 $D$ 가 무엇이건 항상 같이 운반할 수 있다. 유물은 같이 운반하는 것이 이득이기 때문에, $\lfloor N/2 \rfloor$ 개의 보트를 사용하여 유물을 두 개씩 운반하고, 만약 $N$ 이 홀수일 경우 $1$ 개의 유물이 남으니 이는 따로 운반한다. 고로, $N$ 이 짝수일 경우 답은 $\sum B[i]$ 이다. 홀수일 경우 답은 $\sum B[i] + \min(A[i] - B[i])$ 이다.

서브태스크 2 (19점)

$N$ 이 짝수일 경우 $D$ 의 값과 무관하게 답은 항상 $\sum B[i]$ 이다. $2k$ 번 유물과 $2k+1$ 번 유물을 짝지어서 운반하면 되기 때문이다. (인덱스는 $0$-indexed로 표기한다.)

$N$ 이 홀수일 경우 답은 최소 $\sum B[i] + \min(A[i] - B[i])$ 이고, 만약 $D \geq 2$ 라면 이 값을 항상 이룰 수 있다. $A[i] - B[i]$ 를 최소화하는 유물은 따로 보내면, 남은 유물들의 $W[i]$ 차이가 $2$ 이하이기 때문이다. $D = 1$ 이고 $A[i] - B[i]$ 를 최소화하는 유물이 짝수번째 인덱스에 있다면, 양 옆으로 매칭을 해 주면 되니 여전히 그 값을 이룰 수 있다.

즉, 문제가 되는 경우는 $N$ 이 홀수이고, $D = 1$ 이고, $A[i] - B[i]$ 를 최소화하는 유물이 홀수번째 인덱스에 있는 경우이다. 억지로 이 홀수번째 유물을 보내기 위해서는, 무조건 짝수번째 유물을 하나 이상 보내야 한다. 그러면, 그냥 짝수번째 유물 하나만 보내는 것이 이득이다.

고로 $N$ 이 홀수이고 $D = 1$ 인 경우 답은 $\sum B[i] + \min(A[2i] - B[2i])$ 이다.

서브태스크 4 (47점)

최적해에서 쌍으로 같이 보내기로 한 유물들의 집합을 ${i_1, i_2, \ldots, i_{2k}}$ 라고 하자. 집합이 고정되어 있을 때, 이를 보내는 가장 좋은 방법은, $(i_1, i_2), (i_3, i_4)$ 와 같이 인접한 쌍끼리 묶어서 보내는 것이다.

이에 대한 증명은 Exchange argument를 사용하여 할 수 있다. 어떠한 최적해가 $(i_1, i_2), (i_3, i_4), \ldots$ 와 같이 인접한 쌍끼리만 보내다가 처음으로 $(i_{2t+1}, i_u)$ 지점에서 인접하지 않은 쌍을 보냈다고 하자. 대신 $i_{2t+2}$ 는 $(i_{2t+2}, i_v)$ 와 매칭되었다고 하면, 이 매칭을 $(i_{2t+1}, i_{2t+2}), (i_u, i_v)$ 로 보내는 것이 항상 가능함을 알 수 있다. 고로 이러한 쌍들이 보일 때마다 반복해서 바꿔주면 위와 같은 결론에 도달할 수 있다.

이제 동적 계획법으로 문제를 해결할 수 있다. $F[i]$ 를, $0 \ldots i-1$ 번 유물들을 최적으로 보내는 비용이라고 정의하면, $F[i]$ 는 다음과 같은 항들의 최솟값이다:

• $F[i-1] + A[i-1]$
• $F[i-2] + B[i-2] + B[i-1]$ if $W[i-1] - W[i-2] \geq D$
• $F[i-3] + B[i-3] + A[i-2] + B[i-1]$ if $W[i-1] - W[i-3] \geq D$
• $\ldots$
• $F[j] + B[j] + \sum_{k=j+1}^{i-2} A[k] + B[i-1]$ if $W[i-1] - W[j] \geq D$

이 점화식은 $i$ 를 고정하고 $j$ 를 감소 시키면서 풀면 쿼리당 $O(N^2)$ 에 계산할 수 있다.

서브태스크 5 (67점)

사실 위 점화식에서 $j \le i - 4$ 인 경우는 고려할 필요가 없다. 만약에 $i-1$ 번 유물을 $j$ 번 유물하고 같이 보낼 수 있으면, 당연히 $j+1, j+2$ 번 유물도 같이 보낼 수 있고, 이를 통해 비용을 절약할 수 있기 때문이다. 따라서 최적해는 그러한 매칭이 없다고 가정할 수 있다.

고로 $F[i]$ 는 다음 세 항들의 최솟값이다:

• $F[i-1] + A[i-1]$
• $F[i-2] + B[i-2] + B[i-1]$ if $W[i-1] - W[i-2] \geq D$
• $F[i-3] + B[i-3] + A[i-2] + B[i-1]$ if $W[i-1] - W[i-3] \geq D$

이는 쿼리당 $O(N)$ 에 계산할 수 있다.

만점 풀이

위 점화식을 살펴보면, 초기 $D = 0$ 일 때에는 특정 전이들이 제한되다가 $D$ 가 증가하면서 몇 개의 전이들이 가능해짐을 알 수 있다. 전이들을 그래프의 간선으로 본다면, 다음과 같은 식으로 생각할 수 있다:

• $D \geq 0$ 일 때 $(i-1) \rightarrow (i)$ 로 가는 가중치 $A[i-1]$ 의 간선 사용 가능
• $D \geq W[i-1]-W[i-2]$ 일 때 $(i-2) \rightarrow (i)$ 로 가는 가중치 $B[i-2] + B[i-1]$ 의 간선 사용 가능
• $D \geq W[i-1]-W[i-3]$ 일 때 $(i-3) \rightarrow (i)$ 로 가는 가중치 $B[i-3] + A[i-2] +B[i-1]$ 의 간선 사용 가능

동적 계획법을 최적화하는 9가지 방법 (4/4) 에서 소개한 것과 유사하게, DP 점화식을 행렬 곱 형태로 적어서 이를 해결해 보자. 모든 $0 \le i \le N, 0 \le j \le 2$ 에 대해서, $(i, j)$ 를 $i+j$ 번 정점의 복제본이라고 생각하자. 즉, $(i, 0), (i-1, 1), (i-2, 2)$ 는 모두 원래 그래프의 $i$ 번 정점에 대응된다. 이제 $(i-1, *)$ 과 $(i, *)$ 간의 이동에 대한 식으로 모든 전이를 쓸 수 있다:

• $(i-1, j)$ 에서 $(i, j-1)$ 로 항상 이동 가능
• $D \geq 0$ 일 때 $(i-1, 0)$ 에서 $(i, 0)$ 으로 가는 가중치 $A[i-1]$ 의 간선 사용 가능
• $D \geq W[i]-W[i-1]$ 일 때 $(i-1, 0) \rightarrow (i, 1)$ 로 가는 가중치 $B[i-1] + B[i]$ 의 간선 사용 가능
• $D \geq W[i+1]-W[i-1]$ 일 때 $(i-1, 0) \rightarrow (i, 2)$ 로 가는 가중치 $B[i-1] + A[i] +B[i+1]$ 의 간선 사용 가능
• 그 외 항상 불가능

$Cost[i-1][j][k]$ 를 $(i-1, j)$ 에서 $(i, k)$ 로 가는 전이의 비용 (없으면 $\infty$) 이라고 하면, 모든 전이를 $N$ 개의 $3 \times 3$ 행렬로 표현할 수 있고, 두 전이를 합하는 것은 행렬 곱과 유사하게 $A[i][k] = \min(B[i][j] + C[j][k])$ 과 같은 연산으로 가능하다.

이제 모든 간선들을 $D$ 순으로 정렬한 후, 각 간선이 추가될 때마다 간선에 대응되는 행렬 하나를 업데이트 해 주면, 모든 의미 있는 $D$ 에 대해서 문제의 정답을 얻을 수 있다. 각 쿼리를 응답하는 것은, 그 쿼리 이하의 의미 있는 $D$ 최대를 이분 탐색으로 찾고, 그 엔트리에 적힌 정답을 읽어 반환하면 된다.

전체 시간 복잡도는 $O(N \log N + Q \log N)$ 이다.

Problem 2. 메시지 (message)

서브태스크 1 (10점)

Aisha는 Cleopatra의 행동과 상관 없이 무조건 매 패킷으로 1비트를 전송할 수 있다. 만약 Aisha가 모든 패킷을 $1$ 로 채워서 보내면, Basma는 무조건 $1$ 이 $16$개 이상 포함된 패킷을 받고, 만약 Aisha가 모든 패킷을 $0$ 으로 채워서 보내면, Basma는 무조건 $1$ 이 $15$개 이하 포함된 패킷을 받는다.

고로 Aisha는 $M$ 의 각 비트마다, 해당 비트를 $31$개씩 채운 패킷을 보낸다. Basma는 각 패킷을 읽고, $0$ 과 $1$ 중 더 많이 등장한 비트를 적어 메시지를 채운다.

$Q \le 96$ (29.31점)

서브태스크 1의 아이디어를 그대로 사용하는데, $M$ 을 보내는 대신 $C$ 를 보낸다. Aisha는 총 $31$ 패킷을 사용하여 $C$ 의 내용을 전부 보낼 수 있다. 이 정보가 있으면, Basma는 통제되지 않은 비트가 정확히 어떤 비트인지를 알 수 있다. 이후 Aisha와 Basma는 서로 알고 있는 통제되지 않은 비트를 사용하여 통신하면 된다. $64$ 패킷은 $M$, 마지막 패킷은 $M$ 의 길이를 담게 하면, $96$ 개의 패킷을 사용하여 문제를 해결할 수 있다.

$Q \le 84$ (45.75점)

$C$ 를 조금 더 빠르게 보내주자. 오염된 비트는 $15$ 개이니 $C[i] = C[i+1] = 0$ 인 $i$ 가 무조건 존재한다. $5$ 패킷을 사용하여 그 비트 $i$ 의 위치를 보낸다.

이제 남은 값은 $29$ 개 인데, 사실 $28$ 개만 알면 남은 하나는 유추할 수 있으니 $28$ 개의 값을 보내자. $i, i+1$ 번 비트가 손상되지 않음을 알고 있으니, 이 두 비트에다가 정보를 실어서 보내면 된다.

최종적으로 배열 $C$ 를 총 $5+14 = 19$ 패킷으로 보낼 수 있다. 이후 $M$ 을 위에서와 동일하게 $65$ 패킷으로 보내면 45.75점을 얻을 수 있다.

$Q \sim 80$ 정도의 아이디어 (40~60점)

위 풀이를 보면 $C$ 를 더 보내면 보낼수록 Basma가 아는 정보가 많아짐을 알 수 있다. 이를 사용하여 몇 가지 최적화가 가능하다. 예를 들어, Basma가 특정 비트가 오염되지 않음을 안다면, 그 비트를 추가적인 정보 창구로 사용할 수 있다. 반대로, 특정 비트가 오염됨을 안다면, 답을 오염시키는 비트의 후보들이 줄어들고, 고로 "다수결 전략" 을 조금 더 공격적으로 사용할 수 있다 (현재 $T$ 개의 공간이 있고, $B$ 개의 비트가 오염됨을 안다면, $\lfloor \frac{T}{B+1} \rfloor$ 개의 정보를 보낼 수 있음). 이런 식의 최적화로 추가 점수를 얻을 수 있다. 정희우 학생의 풀이가 대략 이런 식이라고 알고 있다.

Cleopatra 입장에서 생각해보면, 모든 비트를 다 바꾼다면 같은 비트를 $31$ 번 반복하는 전략에 막히고, 아무 비트도 안 바꾼다면 $C$ 를 그대로 보내는 전략에 막히는 딜레마가 존재한다. 김은성 학생의 랜덤 알고리즘은 이런 한계점을 이용하여 정보를 보낸다. Aisha와 Basma가 합의 하에 동일한 랜덤 비트를 사용한다고 하자. 각 패킷에 대해서, Aisha는 31개의 랜덤 비트를 먼저 생성하고, 오염된 위치에 이 비트를 $0$ 으로 overwrite해서 Basma에게 보낸다. Basma는 Aisha가 먼저 생성한 랜덤 비트와 실제로 받은 비트를 비교한다. 두 비트가 다르다면, 해당 위치에는 오염이 있다. Aisha는 Basma가 어떤 비트에 대해서 정보를 얻었는지 피드백을 통해서 확인했으니, 모든 비트에 대한 정보가 전달될 때까지 이를 반복한다.

오염된 위치에 있는 두 비트가 같으려면, Cleopatra가 오염된 위치에 둘이 합의한 랜덤 비트를 적었어야 하는데, Cleopatra는 그 비트에 대한 정보가 없기 때문에 이를 성공적으로 수행할 확률이 $1/2$ 이다. 고로 이 알고리즘의 쿼리 횟수 기댓값은 $\log_2 15 \le 4$ 이다. 이렇게 보면 아주 좋은 알고리즘 같지만, 각 입력의 테스트 케이스가 많기 때문에 최악의 경우 호출 횟수는 큰 편이다. (Chernoff Bound로 얻을 수 있는 상한은 $O(\log_2 15 \times \log_2 2100)$ 정도이고 실제로 그 정도의 호출이 일어난다.)

위 아이디어들에서 작은 개선을 할 여지는 많으나, 고득점을 받기 위해서는 공간을 정말 효율적으로 사용해야 하기 때문에 이러한 아이디어 기반으로 많은 점수를 얻을 수는 없다.

여담?

이론 컴퓨터 과학에서, Cleopatra와 같은 상대자를 흔히 Oblivious Adversary 라고 부른다. Cleopatra는 내 알고리즘을 알고 있고 이에 따라 악의적으로 행동할 수 있으나, 내 Randomization에 대해서는 알지 못한다. 이와 별개로, 내 Randomization 까지 알고 있는 상대자를 이론 컴퓨터 과학에서는 Adaptive Adversary 라고 부른다. 이 맥락에서 김은성 학생의 알고리즘은 Oblivious Adversary 에 대해 작동하지만 Adaptive Adversary 에 대해서 작동하지 않는다.

대회에서 흔히 이야기하는 Adaptive Grader는 이 논의의 Oblivious Adversary에 대응됨에 유의하자. 일반적인 대회 문제에서 Adaptive Adversary를 구현하는 것이 기술적으로 가능할지 모르겠다. 다만 srand 를 안일하게 사용하면 Adaptive Adversary에게 한방 먹을 수도 있다.

Oblivious Adversary 는 보통 자료구조의 맥락에서 논의된다. 랜덤성을 사용하는 자료구조가 Oblivious Adversary 에 대해서 작동한다는 것은, 쿼리를 묻는 쪽이 자료구조의 랜덤 시드를 알지 못할 경우 높은 확률로 모든 쿼리에 대해서 올바른/빠른 대답을 준다는 것이다.

직관적으로 생각했을 때, Adaptive Adversary는 너무 비현실적인 가정이고 Oblivious Adversary 정도로도 충분히 올바른 알고리즘이라고 생각할 수 있다. 하지만, Oblivious Adversary에 대해서만 작동하는 자료구조는 Black-box로 쓸 경우 문제를 야기한다. 자료구조가 쿼리에 대해 답을 하는 과정에서, 자신이 사용한 randomization을 흘릴 수 있고, 이를 받아서 사용하는 black-box가 의도하건 의도하지 않건 이를 사용하여 악의적인 쿼리를 생성할 수 있다. (쿼리가 그래프에 따라 "결정된" 경우면 randomization이 유출되지 않겠지만, 예를 들어 경로를 반환하거나 approximated value를 반환하는 경우에는 유출이 가능하다.)

Adaptive Adversary에 대해 작동하는 알고리즘을 구성하는 가장 명료한 방법은 그냥 Deterministic한 알고리즘을 만드는 것이다. 하지만 놀랍게도 Randomization을 사용하면서도 Adaptive Adversary에 대해 작동하는 알고리즘을 구성할 수도 있다. 내가 아는 방법은 크게 두 가지가 있다. 하나는 그냥 적당한 시점에서 자료구조를 재구성 (전체, 혹은 일부) 해서 유출된 randomization과 독립이 되도록 하는 것이다. 다른 하나는 출력에 적당한 노이즈를 주어서 Randomization을 복구하는 것이 대단히 어렵게 하는 것이다 (이러한 기법을 이론에서는 Differential Privacy라고 한다).

$Q \le 71$ (79.64점)

위에서 논의한 알고리즘은 처음에 $C$ 를 전부 보낸 후 $M$ 을 그 다음에 보내는 식으로 작동한다. 그런데 생각해 보면 $C$ 는 모든 커뮤니케이션이 끝난 이후에 알아도 괜찮다. 그 다음에 이전에 받은 메시지들을 읽으면서 $M$ 을 복원하면 되기 때문이다.

$Q \le 84$ 풀이와 동일하게 $C[i] = 0$ 인 위치를 하나 보내는데, 좋은 위치를 두 곳 알 필요는 없다. 오염된 비트는 $15$ 개이니, 첫 $16$ 개 위치 중 $C[i] = 0$ 인 위치가 분명히 존재한다. 고로 이 위치는 $4$ 개의 패킷으로 보낼 수 있다.

이후 $31$ 개의 패킷에서는 $C[i] = 0$ 인 위치를 통해서 배열 $C$ 를 하나씩 보내고, 남은 $C[i] = 0$ 인 위치에는 $M$ 을 $15$ 비트씩 적어서 보낸다. $C$ 를 보낸 것이 완료되면, 남은 $M$, 그리고 $M$ 의 길이를 $16$ 비트씩 적어서 보낸다.

Basma는 첫 $4$개의 패킷을 읽어서 $C[i] = 0$ 인 위치를 찾고, 거기서 $31$ 비트를 읽으면서 $C$ 를 받고, 그 정보를 사용해서 $M$ 을 읽으면 된다.

처음 $C[i] = 0$ 인 위치를 보내는데 $4$ 패킷이 들었고, $C$ 를 보내는 과정에서 $31$ 비트가 밀렸으니 $M$ 을 보내는데 $65+2 = 67$ 패킷이 들었다. 고로 총 $71$ 패킷을 사용한다.

$Q \le 70$ (83.31점)

$M$ 의 길이를 보낼 필요 없이, $M$ 을 무조건 길이 $1025$ 의 비트열로 고정시킬 수 있다. $\sum_{i = 1}^{1024} 2^i \le 2^{1025}$ 이기 때문이다. 구체적인 Construction은 다음과 같다. Aisha는 $M$ 의 마지막 문자의 비트를 뒤집고, 뒤집은 비트를 $M$ 의 길이가 $1025$ 이 될 때까지 맨 뒤에 계속 붙인다. Basma는 $M$ 의 마지막 문자를 읽고, 이 문자로만 이루어진 최대 길이 suffix를 제거한다. 이렇게 하면 Aisha와 Basma는 길이 $1025$ 의 비트열을 사용하여 $M$ 을 주고 받을 수 있다. $1025$ 비트를 보내는 과정에서 $31$ 비트가 밀렸으니, 총 $1056$ 비트를 보내야 하고, 이는 $66$ 패킷으로 가능해서 총 $70$ 패킷을 사용한다.

초기 $4$ 패킷으로 이분 탐색을 하는 과정에서 써도 안전한 여유 공간이 몇 비트 있고, 여기에 $M$ 의 일부를 싣는 식으로 패킷의 수를 더 줄일 수 있다. 다만 100점 풀이의 방향은 아니다.

$Q \le 66$ (100점)

2018/2019 IMO 금메달리스트인 김홍녕 님이 만점 풀이를 제공해 주었다. 김홍녕님은 2019년에도 Broken Line 문제의 풀이를 본인에게 전해준 적이 있다. 아름다운 풀이에 경의를 표한다.

각 $C[i] = 0$ 인 인덱스에 대해서, $nxt(i)$ 를 $C[i+j] = 0$ 인 최소 $j > 0$ 이라고 정의하자 (원형 배열이라고 생각한다. 즉 인덱스를 $\text{mod } 31$ 로 생각한다.) 모든 $C[i] = 0$ 인 인덱스에 대해서 $nxt(i)$ 의 합은 당연히 $31$ 이다.

이제 $C[i] = 0$ 인 인덱스들에 대해서, 첫 $nxt(i) - 1$ 개의 패킷에는 $0$ 을 적고, $nxt(i)$ 번째 패킷에는 $1$ 을 적는다. 이렇게 하면 총 $31$ 비트가 밀린다. 고로 $66 \times 16 - 31 = 1025$ 개의 남은 비트에 $M$ 의 내용을 적으면 된다. 이것이 Aisha의 전략이다.

Basma는 이를 토대로 $C$ 라는 배열을 알 수 있다. Basma는 모든 $0 \le i \le 30$ 에 대해서, $nxt(i)$ 를 $1$ 이 적힌 첫 패킷의 번호로 생각한다. (만약 그런 패킷이 없으면 $67$ 이라고 하자. 아무거나 해도 된다.) 이렇게 하면 $C[i] = 0$ 인 인덱스들에 대해서는 Aisha의 $nxt(i)$ 를 그대로 받을 수 있다. 그렇지 않은 인덱스들에 대해서 노이즈가 있는 것이 문제이다.

이후, 모든 $i$ 에 대해서, $i \rightarrow (i + nxt(i)) \text{ mod } 31$ 로 가는 간선을 만든다. 이 그래프는 Functional graph 이고, 길이 $16$ 의 사이클이 정확히 하나 존재한다. Aisha가 앞에서 만든 게 사이클이고, $15$ 개의 간선으로는 사이클을 하나 더 못 만들기 때문이다.

그리고 그 사이클을 이루는 정점은, 정확히 $C[i] = 0$ 인 정점에 대응된다. 고로 Basma는 $C$ 를 알 수 있고, 이제 Aisha가 준 대로 복호화하면 된다.

정말 아름다운 풀이라고 생각이 든다. 이 풀이의 직관을 어떻게 얻는 지는 잘 모르겠다. 비직관적인 풀이가 난데없이 되는 경우에는, 뜬금없이 functional graph가 튀어나오는 경우가 많지 않았나 하는 감상 정도만 떠오른다.

Problem 3. 트리 (tree)

서브태스크 1 (10점)

계수 개념에 대해서 생각하기 좋은 방향 중 하나는 트리의 리프에서 루트 방향으로 물이 흐른다는 식으로 생각하는 것이다. 모든 노드는 부모 노드 방향으로 $L$ 이상 $R$ 이하의 물을 보낸다. 리프 노드의 경우, 계수 는 부모 노드 방향으로 보낸 물의 양과 동일하다. 리프 노드가 아닌 경우 자식 노드들이 부모 노드 방향으로 $L$ 이상 $R$ 이하의 물을 보냈을 것이다. 계수 만큼 물을 빼거나 물을 더해서, 나도 모은 물들을 부모 노드로 보낸다. $W[i]$ 는, 빼거나 더한 물 $1$ 마다 지불해야 하는 비용이다.

이 비유에서 얻을 수 있는 관찰 하나는 리프 노드가 아닌 경우 물을 더하는 일은 존재하지 않는다는 것이다. 하나 이상의 자식 노드에서 최소 $L$ 의 물이 들어오니, $L$ 이상이라는 조건은 항상 만족된다. 고로 모든 물을 모은 후, $R$ 초과가 되면 물을 빼기만 하면 된다. 다만, 이 때 정확히 $R$ 이 되도록 물을 빼 줄 수도 있고, $R$ 보다 더 낮은 값이 되도록 물을 뺄 수도 있으며, 사실 $R$ 초과가 아니더라도 물을 미리 빼놓고 시작할 수도 있다.

또한, 리프 노드에서 $L$ 초과의 물을 보낼 필요는 없다. 부모 노드에서 물이 부족한 것이 문제가 되지 않기 때문이다.

서브태스크 1에서는, 부모의 $W[i]$ 가 자신의 $W[i]$ 보다 항상 작거나 같다. 리프 노드에서는 $L$ 의 물을 보내는 것이 고정이고, 고로 리프 노드들의 계수는 모두 $L$ 이다. 리프 노드가 아닌 경우, $R$ 초과가 될 때만 $R$이 되도록 물을 빼 주는 것이 항상 이득이다. 그 이상 물을 빼는 것은 부모에서 하는 것이 더 저렴하기 때문이다. 이에 맞춰서 계수를 설정해주는 것이 최적이다. 이러한 전략으로 계수를 설정하고 최소 비용을 계산하는 것은, 쿼리당 한 번의 DFS로 가능하다.

서브태스크 2 (23점)

리프 노드가 아닌 경우 $R$ 보다 더 낮은 물을 보내는 것이 이득일 수도 있다. 자신의 노드의 $W[i]$ 가 작다면 이를 통해 비용 절감을 할 수 있기 때문이다. 서브태스크 1과 마찬가지로 리프가 아닌 노드는 $R$ 이 되도록 물을 빼 주는데, 각 노드에 대해서 $L$ 까지 더 물을 뺄 수 있도록 티켓 을 만들어 주자. 티켓 은, 그 노드에서 물을 얼마나 뺄 수 있는지, 그리고 $1$ 만큼 빼는 데 드는 비용이 얼마인지를 저장한다. 서브태스크 1과 마찬가지로 재귀적으로 문제를 해결하자. 자식 노드에서 물을 $R$ 이하로 빼도록 하고, 추가적으로 티켓 이 발생하면 이들을 모두 모아주자. 현재 노드에서는, 자식 노드의 티켓 의 비용이 $W[i]$ 보다 저렴하다면 이를 이용하여 물을 $R$ 이하로 만들어 주자. 이후, 남은 티켓에 나의 노드의 티켓도 추가하여 현재 서브트리의 티켓 집합 역시 관리해 준다. 티켓을 일반적인 vector로 관리하면 쿼리당 $O(N^2)$ 에 문제를 해결할 수 있다.

서브태스크 3 (41점)

서브태스크 2의 풀이에서 사용하는 티켓 을 Priority Queue와 같은 자료구조에 저장하자. 각 노드에서 자식 노드의 Priority Queue들을 합쳐야 한다. 작은 Priority Queue를 큰 Priority Queue에 넣는 식 (small-to-large) 으로 구현하면, 쿼리당 $O(N \log^2 N)$ 에 해결할 수 있다. Mergeable Heap을 사용하면 $O(N \log N)$ 도 가능하다.

서브태스크 4 (48점)

서브태스크 4의 조건은 서브태스크 1의 조건과 동일하지만 더 강하다. 리프 노드에 대해서는 무조건 $L$ 의 계수가 사용될 것이고, 리프 노드가 아닌 경우 $R$ 초과를 $R$ 로 맞추는 데만 비용이 사용될 것이다. 첫 번째 조건의 비용은 쿼리로 들어와도 쉽게 계산할 수 있지만, 두 번째 조건의 경우는 조금 더 복잡하다. 여기서 중요한 아이디어는, $R$ 초과를 $R$ 로 맞추는 데 드는 비용을 루트 노드에서 전부 지불한다고 생각해도 괜찮다는 것이다. 리프 노드가 아닌 곳에서 물이 $R$ 초과로 흐르는 것은 금지되지만, 여기서 비용을 계산하는 대신 그냥 $R$ 초과로 흐르도록 두고 루트 노드에서 그 비용을 계산하게끔 하자. 그러면 두 번째 조건의 비용은 루트 노드에서 계산할 수 있으며, 거기서 계산되는 비용은, 트리의 리프 노드 개수가 $t$ 일 때 $\max(0, t L - R)$ 이 될 것이다. 고로 답은 $tL + \max(0, tL - R)$ 이 되고, 각 쿼리당 $O(1)$ 에 계산할 수 있다.

서브태스크 5 (59점)

$W[i] = 0$ 인 노드들은 물을 넣거나 빼는 것이 공짜이다. 고로 이러한 노드들은 그것이 리프건 아니건 무조건 $L$ 만큼의 물을 흘릴 것이다. $W[i] = 1$ 인 노드들로 이루어진 연결 컴포넌트를 생각해 보자. 이 컴포넌트들의 리프에서 $L$ 만큼의 물이 발생하고, $W[i] = 0$ 인 자식들에서 $L$ 만큼의 물이 발생한다. $W[i] = 0$ 인 자식은 세기 어려우니, 대신 모든 자식을 센 후 $W[i] = 1$ 인 자식의 개수를 빼자 - 이는, (컴포넌트 크기) - 1 이다. 고로, 각 연결 컴포넌트에서 계산되는 비용은 위와 같이 $tL + \max(0, uL - R)$ 꼴이다. $tL$ 은 쉽게 계산할 수 있다. $\max(0, uL - R)$ 꼴의 합은 $u \geq \frac{R}{L}$ 인 모든 $u$ 에 대해서 $(\sum u) \times L - (\sum 1) \times R$ 과 동일하다. 고로 $u$ 들을 크기 순으로 정렬하고 부분 합 배열을 구성하면, 각 쿼리에서 이분 탐색을 통해서 $u \geq \frac{R}{L}$ 인 첫 지점을 찾고 합을 구할 수 있다. 고로 각 쿼리당 $O(\log N)$ 에 계산할 수 있다.

만점 풀이

사실 (거의) 일반성을 잃지 않고 $L = 1$ 이라고 가정할 수 있어서 서브태스크 6은 잘못 만들었다고 생각이 든다. 바로 만점 풀이로 넘어간다.

KOI 2023 고등부 4번이나 UCPC 2024 G번과 유사한 아이디어를 사용한다. 구체적으로, $W[i] \le 1$ 인 케이스를 풀면, 사실상 전체 문제를 푼 것이나 마찬가지라는 것을 보일 수 있다. 모든 $1 \le x \le 1,000,000$ 에 대해서, $W[i] \le x - 1$ 일 경우 $W^\prime[i] = 0$, 아니면 $W^\prime[i] = 1$ 로 비용을 배정하고 서브태스크 5의 방식으로 문제를 해결하자. 이 때의 답을 모든 $x$ 에 대해서 합하면, 이는 전체 문제의 답과 동일하다.

대략의 직관은 비용이 $W[i]$ 일 경우 $x \le W[i]$ 일 때마다 비용을 1씩 지불하니까 지불하는 비용 합은 같다는 식이다. 구체적으로 알고리즘이 왜 정당한지를 살펴보기 위해, 서브태스크 2/3의 그리디 풀이를 생각해 보자. $W[i]$ 의 대소 관계만이 모든 판단의 기준이 되고, $W[i]$ 가 작은 원소를 우선시하는 식으로만 알고리즘이 설계되어 있다. 위와 같은 식으로 문제를 분해하고 이를 똑같은 그리디로 해결한다고 하자. 어떠한 비용 $W[i]$ 의 원소가 특정 시점에 티켓으로 들어갔다고 하고, 그리디 알고리즘이 이 원소를 뽑았다 하자. $x \le W[i]$ 인 경우의 0-1 인스턴스에서도 모두 이 원소에 대해 $1$의 비용이 지불되었다고 생각할 수 있다. $x$ 보다 작은 (고로 $W[i]$ 보다 작은) 원소들이 확실히 동이 났기 때문이다. $W[i] + 1\le x$ 인 경우에는 반대로, 이 원소에 대해 $0$의 비용이 지불된다 없다. 고로, 분해된 문제에서의 그리디 최적해는 무조건 원래 문제에서의 그리디 최적해와 동일한 결정을 따른다.

이제 전체 문제를 $1000000 \times N$ 의 전처리와 $O(\log N)$ 의 쿼리 시간으로 해결할 수 있다. 모든 $x$ 에 대해서 서브태스크 5의 풀이를 다 실행시키고, 이분 탐색으로 합을 해 주면 되기 때문이다.

이를 $O(N \log N)$ 정도의 전처리로 최적화하려면, 각 컴포넌트를 매번 합해주는 대신 컴포넌트에 갱신이 있을 때만 합해주어야 한다. 구체적으로, 초기 $x$ 가 아주 큰 상태에서 시작해서, $x$ 를 점차 감소시키면서 문제를 해결하자. 이는 초기 $W[i] = 0$ 인 상태에서 특정 정점들에 대해 $W[v] = 1$ 을 배정하면서 $1$ 의 연결 컴포넌트들을 키우는 풀이라고 생각할 수 있다.

컴포넌트들을 Union-find로 관리하자. 특정 정점에 대해서 $W[v] = 1$ 이 배정될 경우, 두 개 이상의 컴포넌트가 서로 합쳐질 수 있다. 해당 컴포넌트가 생겼던 때의 $x$ 와, 현재의 $x$ 의 차가 해당 컴포넌트의 기여량이니, 이후 쿼리에서 이 기여량을 곱해서 답에 합하면 된다. Union-find를 사용하면 컴포넌트의 차수 합, 리프 개수 합, 생겼던 시점 등 필요한 정보를 모두 관리할 수 있다.

각 쿼리마다 구해야 하는 것은 $tL + c \times \max(0, uL - R)$ 형태의 합이다. 여기서 $c$ 는 위에서 얘기한 컴포넌트의 기여량이다. 서브태스크 5와 동일하게 이분 탐색 + 부분합으로 해결할 수 있다.

시간 복잡도는 $O((N+Q) \log N)$ 이다.