IOI 2025 Day 1

볼리비아 수크레에서 IOI 2025 Day 1 대회가 진행되었다. Day 1 기준 한국 학생들의 성적은 다음과 같다.

• 우민규, 100 / 99.33 / 93, 292.33점, 4등
• 정민찬, 100 / 79.77 / 100, 279.77점, 5등
• 이유찬, 100 / 58.89 / 86, 244.89점, 20등
• 변재우, 39 / 76.25 / 86, 201.25점, 60등

Day 1 현재, 한국 팀의 성적이 대단히 좋다. 팀 전체적으로 보아도 결과가 좋은 편이고, 우민규 학생과 정민찬 학생은 만점에 대단히 근접한 점수를 받아 개인 성적 면으로도 아주 우수하다. 다음 날 안정적으로만 대회에 임하여도 금메달을 확정할 수 있고, 그보다 더 높은 목표도 노릴 수 있는 수준이다. 변재우 학생은 금메달권에서 약 30~40점 정도 벗어나 있는데, 다음 날 문제가 아주 어렵지만 않으면 충분히 극복 가능한 수준이다. 연습이나 다른 대회에서 이미 좋은 성적을 많이 보여준 학생이라 기대해 봄직하다.

Day 1의 만점자는 중국의 Hengxi Liu 학생이다. 네 명의 중국 학생들 모두 만점에 상당히 근접해 있어서, 올해도 강한 결과가 예상된다. Day 1 상위 다섯 참가자는 중국의 Hengxi Liu, Xinyang Chen, Haifeng Liu, 그리고 한국의 우민규 정민찬이다. 그 뒤를 캐나다의 Ryan Bai와 중국의 Sizhe Fan이 잇는다.

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

Day 1 Problems PDF

souvenir-en.pdf

0.15MB

souvenir-ko_KR.pdf

0.25MB

triples-en.pdf

0.16MB

triples-ko_KR.pdf

0.33MB

worldmap-en.pdf

0.16MB

worldmap-ko_KR.pdf

0.25MB

Problem 1. 선물 (souvenir)

서브태스크 2 (3점)

$P[i]$ 의 값을 모두 알고 있다면, 모든 $i$ 에 대해 transaction(P[i]) 를 $i$ 번 호출함으로써 문제의 목표를 달성할 수 있다.

서브태스크 1 (7점)

transaction(P0 - 1) 을 호출하면 무조건 $1$ 번 선물을 하나 사게 되고 문제의 목표가 자동으로 달성된다. 이 알고리즘은 이 서브태스크를 풀 수 있는 유일한 방법이다: 문제 조건에 의해 $P[1] \le x \le P[0] - 1$ 을 만족하지 않는 $x$ 를 호출하면 바로 오답 처리가 되는데, $P[1]$ 을 모르는 상황에서 부를 수 있는 값이 $P[0] - 1$ 이외에는 존재하지 않는다.

서브태스크 4 (25점)

서브태스크 1에서 언급했듯이 값에 대한 정보가 없는 상황에서 호출할 수 있는 유일한 함수는 transaction(P0 - 1) 이다. 이 함수의 반환값에 따라서 케이스를 나누자:

• 함수가 $1$ 번 선물을 사지 않았다: 이런 경우는 불가능하다. $P[1] \leq P[0] - 1$ 이기 때문이다.
• 함수가 $1$ 번 선물을 샀다: 거스름돈의 값으로 $P[1]$ 을 유추할 수 있다. transaction(P[1] - 1) 을 $2$ 번 호출하면 된다.
• 함수가 $1, 2$ 번 선물을 샀다: 거스름돈의 값으로 $P[1] + P[2]$ 를 유추할 수 있다. $P[1] > P[2]$ 이기 때문에 $P[2] < \frac{P[1] + P[2]}{2} < P[1]$ 역시 만족한다. transaction((P[1] + P[2]) / 2) 를 호출하면, 이 함수가 $2$ 번 선물을 살 것이다.만점 풀이

서브태스크 3, 5의 풀이가 만점 풀이와 연관이 있다고 생각하지 않는다. 서브태스크를 나누기 적합한 종류의 문제는 아니라고 생각한다.

특정 값을 호출하게 되면, 인터랙터는 선물의 부분집합, 그리고 그 부분집합에 속하는 선물의 비용 합 (호출 인자 - 나머지) 를 반환한다고 볼 수 있다. 즉, 각 함수 호출에서 반환하는 것은 $p[i]$ 항들의 합으로 이루어진 등식이다. 초기에는 $p[0] = p0$ 이라는 형태의 등식이 주어진다.

각 등식의 번호 를, 해당 등식에 등장하는 가장 작은 선물의 인덱스로 정의하자. $0, 1, \ldots, N -1$ 번 등식이 모두 있다면, $N - 1$ 번 등식에서 $p[N - 1]$ 을 구하고, $N - 2$ 번 등식에서 $p[N - 1]$ 을 토대로 $p[N - 2]$ 를 구하고 ... 를 반복해서 모든 $p[0], p[1], \ldots, p[N-1]$ 을 구할 수 있다. 또한 $i$ 번 선물은 최대 $i$ 개의 등식에 등장하니, 사지 않은 횟수만큼은 transaction(p[i]) 를 호출해서 충당할 수도 있다. 즉, 이러한 등식을 얻을 수만 있으면 문제가 해결된다. (말고는 문제를 풀 수 있는 방법이 거의 없다: $1$ 번 등식을 얻게 되면 $1$ 번 선물에 대해 다시 얻을 수 있는 정보는 없으니, $2$ 번 등식을 얻어야만 하고, $2$ 번 등식을 얻으면...)

이제 저러한 등식을 얻는 것을 목표로 하자. 오답 처리를 받지 않게끔 함수 호출을 하려고 하면 할 수 있는 호출의 경우가 그렇게 많지 않다. 크게 두 가지 경우가 있다:

• (Case 1) 마지막 호출이 $p[x]$ 의 값을 공개했다면, $p[x] - 1$ 을 호출해서 $x+1$ 번 등식을 찾느다.
• (Case 2) 마지막 호출이 $S=p[x_1] + p[x_2] + \ldots + p[x_k]$ 을 공개했다면, $S / k$ 를 호출해서
  초기 상태에서 우리가 아는 값은 $p[0]$ 이니, Case 1을 사용하여 transaction(p[0] - 1) 을 호출한다. 이 과정에서 반환된 부분집합의 크기가 $1$ 이라면 Case 1을, 아니라면 Case 2를 호출해서, 더 큰 선물에서 시작하는 등식을 찾는다. 또한, 이를 사용한다면 최후에는 $N-1$ 번 등식을 무조건 얻는다.

이제, $i \le N - 2$ 에 대해서 $p[i + 1], p[i + 2], \ldots, p[N - 1]$ 을 모두 알고 있다고 할 때 $p[i]$ 를 얻는 방법을 생각해보자. 만약에 $i$ 번 등식이 있다면, $p[i]$ 를 결정할 수 있으니 바로 해결이 된다. $i$ 번 등식이 없는 경우, $j$ 를 $j$ 번 등식이 존재하는 최대 $j < i$ 라고 정의하자. 두 가지 사실을 알 수 있다:

• $j$ 번 등식은 Case 2로 얻었다.
• $j$ 번 등식을 이루는 선물이 $x_1 = j, x_2, \ldots, x_k$ 라고 하면, $x_k \geq i + 1$ 이다. $p[x_k] \leq S / k$ 이기 때문에, $S / k$ 를 호출하면 무조건 $x_k$ 이하의 인덱스를 가지는 선물이 포함되고, $j +1, \ldots, i$ 번 등식이 없으니 그 인덱스는 $i+1$ 이상이기 때문이다.

고로, $j$ 번 등식에서 몇 개의 변수는 우리가 이미 알고 있고, 제거할 수 있다. 이렇게 되면, $j$ 번 등식을 이루는 모든 변수는 $j = x_1 < x_2 < \ldots < x_k \leq i$ 를 만족한다. $j$ 번 등식에 대해서 Case 1과 Case 2를 반복해서 호출하면, 무조건 $i$ 번 등식을 얻을 수 있다.

• Case 1 호출로 $i$ 번 등식을 건너뛸 수는 없다.
• Case 2 호출에서 공개된 변수가 $i$ 번 초과라면, 모두 이미 알려진 값을 사용해서 제거해 주자. 등식의 모든 변수가 $i$ 번 이하이니, 다음 호출에서 불려지는 등식은 $i$ 번 이하이다.

고로, $i$ 번 등식을 채울 수 있고, $p[i]$ 역시 계산할 수 있다. 이를 $i$ 가 감소하는 순으로 반복하면 모든 값을 구하고 문제를 해결할 수 있다.

Problem 2. 3개의 봉우리 (triples)

서브태스크 1 (8점)

모든 $i, j, k$ 를 시도하면 $O(N^3)$ 시간에 문제가 해결된다.

서브태스크 2 (14점)

$i$ 를 고정하면, 가능한 $j, k$ 가 모두 $i + 10$ 이하이다. 아닐 경우, $d(i, j) > 10$ 혹은 $d(i, k) > 10$ 일 텐데, 이에 해당하는 $H$ 값이 존재하지 않는다. 고정된 $i$ 에 대해 $100$ 개 이하의 후보를 모두 시도하면 $O(N)$ 시간에 문제가 해결된다.

서브태스크 3 (24점)

$i, j$ 를 고정하자. 집합 ${H[i], H[j], H[k]}$ 가 ${j - i, k - i, k-j}$ 와 일치한다는 것은, ${H[i], H[j]}$ 와 ${k - i, k - j}$ 에 동시에 속하는 원소가 존재함을 뜻한다. 고로 가능한 $k$ 의 후보가 $4$ 개로 좁혀져서, 모든 후보를 시도해 볼 수 있다. $O(N^2)$ 시간에 문제가 해결된다.

서브태스크 4 (35점)

$H[i]$ 는 ${j - i, k- i, k- j}$ 중 하나가 성립한다. 케이스를 나눠보자:

• $H[i] = j - i$ 인 경우에는 $j = i + H[i]$ 이다. 가능한 $(i, j)$ 의 후보가 최대 $N$ 개이니 서브태스크 3의 풀이를 사용하여 문제를 해결할 수 있다.
• $H[i] = k - i$ 인 경우에는 대신 $k = i + H[i]$ 가 되는데, 이 경우에도 서브태스크 3의 풀이를 동일하게 적용할 수 있다.
• $H[i] = k - j$ 인 경우:
  • $H[j] = j - i, H[k] = k - i$ 인 경우: $j$ 를 고정하면 $i = j - H[j]$ 로 고정되어서 서브태스크 3의 풀이를 다시 적용할 수 있다.
  • $H[j] = k - i, H[k] = j - i$ 인 경우: 하나를 고정한다고 다른 수가 정해지지 않아서 상당히 까다롭다. 하지만 $j < k, H[j] > H[k]$ 가 성립하고, 이는 이 서브태스크에서 존재하지 않음이 보장되어서 고려할 필요가 없다.

총 $O(N)$ 개의 답의 후보가 있다. std::set 등을 사용해서 중복을 제거하면, 전체 문제가 $O(N \log N)$ 시간에 해결된다. (중복 제거를 $O(N)$ 에 할 수 있는 방법이 여럿 있지만 필요하지 않다.)

Part I 만점 풀이 (70점)

서브태스크 4의 풀이에 따라서, $H[i] = k - j, H[j] = k - i, H[k] = j - i$ 을 제외한 모든 경우를 $O(N)$ 시간에 계산할 수 있다. 최종적으로 저 경우를 빠르게 계산하는 것이 문제의 목표가 된다. 이 경우가 골치아픈 것은, 하나의 인자를 고정해서 얻을 수 있는 정보가 너무 한정적이라서 조건을 만족하는 $(j, k)$ 를 세기가 어렵다는 것이다.

현재 상황을 그림으로 그리면, 다음과 같다:

$H_k, H_i$ 가 아니라 $H_i, H_k$ 면 연관된 변수들이 붙어있으니 편해 보인다. 일단 다짜고짜 바꿔보자.

지금 한 변환이 구체적으로 무엇일까? $j^\prime$ 을, $j$ 를 $(i+k)/2$ 를 기준으로 대칭시킨 위치 - 즉, $j^\prime = i + k - j$ 로 정의하자. $i + H[i] = k - H[k] = j^\prime$ 이 성립하니, $j^\prime$ 이 고정되었을 때 고려하게 되는 $(i, k)$ 의 쌍이 비교적 다루기 쉬운 형태이다. 각 $j^\prime$ 에 대해, $In(j^\prime) = {i | i + H[i] = j^\prime}, Out(j^\prime) ={k | k - H[k] = j^\prime}$ 이라고 하자. 이제 모든 $0 \le j^\prime \le N - 1$ 에 대해서, $i \in In(j^\prime), k \in Out(j^\prime)$ 을 모두 열거한 후 이에 따라 유일하게 결정되는 $j = i+k-j^\prime$ 이 문제 조건을 만족하는지를 확인하면 된다.

이 알고리즘의 시간 복잡도는 $\sum_{j^\prime} |In(j^\prime)| \cdot |Out(j^\prime)| = O(N^2)$ 이다. 만약 각 $i$ 와 $k$ 가 비교적 균등하게 분포되어 있어서 $In(j^\prime), Out(j^\prime)$ 의 크기가 작으면 알고리즘은 충분히 빠르지만, 어떠한 $j^\prime$ 에 $i$ 와 $k$ 가 몰려있게 된다면 이러한 이점이 사라진다. 구체적으로, 만약 모든 $j^\prime$ 에 대해, $\min(|In(j^\prime)|, |Out(j^\prime)|) \leq b$ 가 만족한다면, 이 알고리즘은 $O(bN)$ 시간에 작동한다.

$|In(j^\prime)|, |Out(j^\prime)|$ 이 모두 $b$ 초과인 $j^\prime$ 은 최대 $N / b$ 개 존재한다. 이러한 $j^\prime$ 에 대해서는, $j$ 를 대신 고정하자. 이 경우, $i + k = j^\prime + j, k - i = H[j]$ 를 만족해서, 가능한 $(i, k)$ 가 유일하게 고정된다. 고로, 이러한 케이스들을 모두 $O(N^2 / b)$ 시간에 처리해 줄 수 있다. $b = \sqrt N$ 으로 정할 경우, 전체 문제는 $O(N \sqrt N)$ 에 해결된다.

Part II 만점 풀이 (100점)

70점 풀이에서, 모든 올바른 쌍 $(i, j, k)$ 는 $i + H[i] = k - H[k]$ 를 만족함을 볼 수 있다. 사실, 이 조건만을 만족하는 것이 아니고, 모든 올바른 쌍 $(i, j, k)$ 는 다음 조건들을 전부 만족한다:

• $i + H[i] = k - H[k]$
• $j + H[j] = k + H[k]$
• $i - H[i] = j - H[j]$

더불어 이 세 조건을 전부 만족하면 $(i, j, k)$ 가 올바른 쌍이라는 것도 보일 수 있다.

모든 $0 \le i \le N - 1$ 에 대해, $(i - H[i], i + H[i])$ 를 잇는 방향성 간선을 그리자. 당연하지만 이 그래프는 DAG이다. 올바른 쌍 $(i, j, k)$ 는, 이 방향 그래프에서의 삼각형 (즉, 1 -> 2, 2 -> 3, 1 -> 3)에 대응된다. DAG에 유효한 정점이 $\sqrt N$ 개 정도이고, DAG가 거의 완전 그래프의 형태를 띈다면, 이 DAG 위의 삼각형의 개수는 $N \sqrt N$ 개 정도가 되어 답도 그 정도가 될 것이다.

고로, $S = {i - H[i] | 0 \le i \le N - 1} \cup {i + H[i] | 0 \le i \le N - 1}$ 의 크기가 $\sqrt N$ 정도인 수열 $H$ 를 구성해 보자. $S$ 의 원소를 $x_1, x_2, \ldots, x_b$ 라고 둔다면 $(b = O(\sqrt N))$, $i - H[i] = x_j, i + H[i] = x_k$ 가 만족할 것이다. 이를 정리하면, $i = \frac{x_k + x_j}{2}, H[i] = |\frac{x_k - x_j}{2}|$ 가 성립한다. 짝수 $x_1, x_2, \ldots, x_b$ 를 랜덤하게 고른 후, 위와 같은 대응 관계를 그리디하게 만들어 주자 (당연히 한 $i$ 에 대응되는 $H[i]$ 값이 $1$ 개가 아닐 수 있으나 대충 $1$ 개를 아무거나 골라준다).

$b = \lfloor 4 \sqrt N \rfloor$ 으로 잡고, $x_i$ 를 $[-M/8, 9M/8]$ 범위의 서로 다른 짝수로 샘플링한 후 1.9초만 돌려도 99.8225점이 나온다. 만점이 안 나오는 유일한 케이스는 서브태스크 8인데 ($T = 1929$), 이 케이스는 따로 로컬에서 계산하면 된다. 내 컴퓨터에서는 계산하는 데 11분 이내로 걸렸다.

Problem 3. 세계 지도 (worldmap)

Subtask 1 (5점)

$K = N$ 으로 두고 $i$ 번 행에 $i$ 를 적으면 된다.

Subtask 2 (15점)

$K = 2N - 1$ 으로 두자. 아무 정점에서 DFS를 시작한 후 재귀적으로 구성하자.

리프의 경우 자신을 적은 $1 \times 1$ 격자를 반환한다.

리프가 아닌 경우, 각 자식의 서브트리 크기가 $c_1, c_2, \ldots, c_k$ 라고 하자. 재귀적으로, $(2 c_i - 1) \times (2 c_i - 1)$ 크기의 격자를 구성한다. 이제 $(2 \sum c_i + 1) \times (2 \sum c_i + 1)$ 크기의 격자를 반환하는데, $i$ 번 격자의 왼쪽 위 모서리가 $(1,2 \sum_{j < i} c_j + 2)$ 에 닿게끔 한다. 이렇게 하면 각 격자가 차지하는 열이 $[2 \sum_{j < i} c_j + 2, 2 \sum_{j \le i} c_j ]$ 의 구간을 이뤄서, 각 격자 사이에 한 열이 비게 되고, 시작과 끝 열도 비게 된다. 빈 셀에는 모두 자신의 번호를 적으면 된다.

Subtask 3 (22점)

$K = 2N$ 으로 두고, $2i+1, 2i+2$ 번 행에 $i$ 를 적은 후, $2j+1, 2j+2$ 번 열에 $j$ 를 덮어씌워 적으면 된다.

22점 초과의 풀이는 준비중입니다. ㅠㅠ