IOI 2025 Day 1

(25/08/10: worldmap 풀이 추가)

볼리비아 수크레에서 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 ]$ 의 구간을 이뤄서, 각 격자 사이에 한 열이 비게 되고, 시작과 끝 열도 비게 된다. 빈 셀에는 모두 자신의 번호를 적으면 된다.

트리의 Euler tour를 사용하면 이 풀이를 간단하게 구현할 수 있다. DFS를 통해서 각 정점의 깊이를 계산하고, 다음과 같이 DFS ordering을 구하자:

void dfs(int x, int p) {
    din[x] = seq.size();
    seq.push_back(x);
    for (auto &y : gph[x]) {
        if (y != p) {
            dfs(y, x);
            seq.push_back(x);
        }
    }
    dout[x] = seq.size();
}

DFS가 종료된 후 seq 의 길이는 총 $2N-1$ 이며, 위에서 설명한 구성의 1행을 읽었을 때 적혀있는 번호가 seq 에 저장된 정점 인덱스랑 일치함을 알 수 있다. 추가적으로, 위에서 설명한 구성에서 각 정점에 대응되는 격자 영역은 $din[v] + 1, din[v] + 2, \ldots, dout[v]$ 번 열에 존재함 역시 알 수 있다. 따라서, 각 정점을 깊이가 증가하는 순서대로 정렬한 후, $v$ 번 정점에 대해 $[2 depth(v) + 1, 2N - 1] \times [din[v] + 1, dout[v]]$ 직사각형 영역 (1-based) 에 $v$ 라는 값을 적어주면 된다.

Subtask 3 (22점)

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

$K = 3N$ (86점)

연결 그래프가 아니면 답이 존재하지 않는다. 아무 컴포넌트를 잡자. 이 컴포넌트에 속하는 셀은 지도를 전부 덮지 못하여, 컴포넌트에 속하지 않는 셀과 인접할 수 밖에 없어진다.

연결 그래프일 경우 답이 항상 존재한다. 사실, 서브태스크 2의 풀이를 조금만 변형하여도 대단히 높은 점수를 얻을 수 있다. 임의의 정점에서 시작해서 DFS를 하고, 스패닝 트리를 서브태스크 2의 방식으로 그리자. 이렇게 할 경우 back edge들이 지도에 반영되지 않는다. DFS 트리의 모든 back edge $(u, v)$ 는, $u$와 $v$ 가 조상 관계를 이룬다. $u$ 가 $v$ 의 조상이라고 하고, $u$ 에 대응되는 직사각형 위에 이러한 back edge를 그린다.

$S_u$ 를 $u$ 를 루트로 한 서브트리의 크기라고 하자. 서브태스크 2에서 사용한 구성을 보면, $u$ 만으로 구성된 크기 $2 \times (2 S_u - 1)$ 크기의 직사각형이 각 영역 맨 위에 존재한다. 이 직사각형의 크기를 $3 \times (2 S_u - 1)$ 로 늘리면, 두 번째 줄의 짝수 번째 행들에 총 $S_u - 1$ 개의 셀을 인접하지 않게 나열할 수 있다. $u$ 를 조상으로 가질 수 있는 $v$ 의 개수는 정확히 $S_u - 1$ 개이니, 각각의 셀에 반대쪽 끝점 $v$ 를 적으면 모든 back edge를 표현할 수 있다.

직사각형의 크기를 $3 \times (2 S_u - 1)$ 로 키워야 하기 때문에, 각 정점 $v$ 에 대응되는 직사각형 영역은 $[3 depth(v) + 1, 3N] \times [din[v] + 1, dout[v]]$ 로 설정한다. 이렇게 하면 $3N \times (2N - 1)$ 크기의 격자를 얻게 되고, $1$ (정확히는 DFS를 시작한 루트) 로 구성된 $N+1$ 개의 열을 옆에 씌워주면 정사각형으로 이를 변환할 수 있다.

만점 풀이

$K = 3N$ 풀이를 조금만 변형하면 아주 깔끔한 만점 풀이를 얻을 수 있다.

첫 번째 변형에서는 86점 풀이의 구성을 단순화한다. 현재 86점 풀이에서는 각 정점 $u$ 에서 내려가는 back edge들을 서로 인접하지 않게끔 배정한다. 고로, 각 $u$ 에 대해 반대쪽 끝점 $v$ 가 어디 배정되는지를 따로 계산해 줘야 한다. 이렇게 하지 말고, 항상 $din[v] + 1$ 번째 셀에 정점 $v$ 를 배정하자. $v$ 가 $u$ 의 서브트리에 있기 때문에 $v$ 는 무조건 직사각형 영역 안에 들어간다. 위 배정을 통해서 두 정점 $v_1, v_2$ 가 인접한 셀에 놓이게 된다 해도, 이들은 Euler tour 상에서 애초에 인접하기 때문에 문제가 되지 않는다.

두 번째 변형에서는 back edge를 놓는 직사각형의 크기를 줄인다. 86점 풀이에서 우리는 back edge를 올리기 위해서 직사각형의 행 개수를 $3N$ 으로 늘렸다. 이걸 원래대로 되돌리고, 정점 $v$ 에 대한 직사각형 영역을 $[2 depth(v) + 1, 2N] \times [din[v] + 1, dout[v]]$ 로 설정하자.

행 개수를 줄이면 어떤 문제가 생길까? $u$ 를 조상으로 하는 back edge $(u, v)$ 에 대해, $v$ 의 아래로 인접한 셀이 $u$ 의 자식 $c$ 에 대응되고, $v$ 는 $c$ 와는 인접하지 않음에도 간선이 생길 수 있다. 그런데, $v$ 가 $c$ 와 인접하지 않다면, 아래 두 칸이 모두 $c$ 로 적혀 있을 것이다. 고로 이 중 $v$ 에 인접한 칸을 그냥 $u$ 로 고쳐 적어도 문제가 없다. 즉:

u
v
c
v
...

일 경우 어차피 $v$ 와 $c$ 가 인접하니까 두 줄이어도 상관이 없고

u
v
c
c
...

일 경우 $c$ 가 두 칸을 먹고 있는 것이 낭비이니

u
v
u
c
...

로 수정해도 된다는 것이다. 즉, Back edge $(u, v)$ 에 대해, $u$ 의 $v$ 방향 자식 $c$ 가 $v$ 와 인접하지 않으면, $v$ 와 인접한 $c$ 셀을 $u$ 로 고쳐 적으면 된다. 이 부분만 고치면, 만점이 나온다.