IOI 2020 Day 2

(2020/09/24 23:47 - 원문 작성)
(2020/09/29 01:20 - 4번 문제 풀이를 추가했다.)
(2022/08/02 02:13 - 5번 문제의 100점 풀이를 추가했다.)

IOI 2020 Day 2 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다.

• 최은수, 100 / 100 / 100 / 100 / 93.00 / 100, 593.00점, 2등 (금메달)
• 송준혁, 75 / 100 / 100 / 100 / 92.62 / 65.32, 532.94점, 12등 (금메달)
• 임성재, 44 / 100 / 41 / 100 / 92.24 / 100, 477.24점, 30등 (은메달)
• 반딧불, 32 / 100 / 53 / 21 / 80.14 / 100, 386.14점, 61등 (은메달)

올해 한국 학생들의 개인 성적이 매우 우수한 편이다. 특히, 최은수 학생은 만점에서 7점 차이밖에 나지 않는 593점의 성적으로 전체 2등을 하였다. 이는 2015년 이후 첫 Top 5 성적이기도 하다. 축하합니다! 송준혁 학생도 12등이라는 상당히 높은 성적으로 마무리하였다. 임성재 학생은 Day 2에 만점에 가까운 점수를 얻어 거의 금메달에 근접했으나, 정말 아쉽게도 30등으로 마무리하였다. 30등은 은메달 중 가장 높은 성적으로, 작년 이온조 학생의 비슷한 결과가 떠오른다. 올해 Day 2는 높은 점수를 얻기가 예년 비해 쉬운 편이라, 아주 좋은 성적을 내었음에도 크게 돋보이지 못한 것이 아쉽다.

송준혁 학생과 반딧불 학생의 경우 내년에도 IOI를 참가할 수 있는 기회가 있으며, 반딧불 학생의 경우 내후년도 가능하다. 향후 한국 팀의 성과가 기대된다. 한국 팀의 팀 성적은 2금 2은으로, 높은 개인 성적에 비하면 약간 아쉬운 감이 있지만, 여전히 좋은 결과다.

이번 IOI의 1등은 William Lin으로, 600점 만점으로 모든 문제를 해결하였다. 축하합니다! 오랜만에 만점으로 마무리 된 IOI라는 점에서 알 수 있듯이, 전반적으로 평년에 비해서 쉬운 느낌이 있다. 최상위권을 가르는 수단이 mushrooms의 10점 남짓한 부분점수 뿐이었다는 것은 아쉽다.

Day 2 Problems PDF

day2-biscuits-ISC.pdf

0.33MB

day2-mushrooms-ISC.pdf

0.28MB

day2-notice-ISC.pdf

0.14MB

day2-stations-ISC.pdf

0.47MB

day2-biscuits-ko_KR.pdf

0.32MB

day2-notice-ko_KR.pdf

0.17MB

day2-mushrooms-ko_KR.pdf

0.32MB

day2-stations-ko_KR.pdf

0.52MB

구현한 코드는 (만약 존재한다면) https://github.com/koosaga/olympiad/tree/master/IOI 에 모두 올라와 있다.

Problem 4. 비스킷 담기

Problem

안티 콩에게는 $k$ 종류의 비스킷이 있다. 이 중 $i$ 번 종류 ($0 \le i \le k - 1$) 의 비스킷은 맛이 $2^i$ 이고, 그 개수가 $A[i]$ 개 이다. ($0 \le A[i] \le 10^{18}$).

안티 콩은 $x$ 명이 참가하는 대회에 이 비스킷들을 나눠주려고 한다. 이 때 $x$ 명이 먹는 비스킷의 맛의 합은 동일해야 한다. 모든 비스킷을 사용할 필요는 없으며, 비스킷을 아예 안 줘도 된다. 맛의 합을 $y$ 라고 했을 때, 가능한 서로 다른 $y$ 의 개수를 세어라. 모든 비스킷의 맛의 합은 $10^{18}$ 을 넘지 않는다.

Solution

일반적인 OI-style과는 약간 거리가 있는 수학 문제 타입의 문제이다. 사실 $2^i$ 의 맛을 가진 비스킷으로 냅색을 하는 문제는 몇 번 대회에 나온 적이 있기 때문에 (NEERC 2012 Exact Measurement) , 상당히 전형적인 스타일의 문제로 보인다. 이런 점을 빼면 문제 자체로는 흥미로운 편이다.

Subtask 1 (9점)

총 맛의 합이 $10^5$ 를 넘지 않기 때문에, 모든 가능한 $y$ 에 대해 Brute-force를 시도해 볼 수 있다. 고로 $x$ 명의 사람에게 $y$ 만큼의 비스킷을 나눠주는 packing이 가능한 지를 살펴야한다. 어떠한 값 $2^i$ 를 큰 비스킷 하나를 사용해서 채운 경우와, 작은 비스킷 여러개를 사용해서 채운 경우를 비교해 보자. 큰 비스킷을 사용해서 채우는 것은 작은 것으로 대체할 수 있으나, 작은 비스킷이 여러 사람을 채우고 있으면 이를 큰 비스킷으로 대체하는 것은 불가능하다. 고로 그리디하게, 큰 비스킷부터 채우는 것이 이득이다.

결론적으로, 큰 비스킷부터 서대로 $x$ 명의 사람들에게 최대한 많이 나눠주고, 이후 모두 $y$ 를 채웠는지 보면 된다. 한 종류의 비스킷을 나눠줄 때, 누구한테 몰아서 나눠주던 최대한 공평하게 나눠주던 상관이 없으니, 정말 아무렇게나 나눠줘도 된다. 그리디의 시간 복잡도는 $O(kx)$ 정도일 것이고, 가능한 $y$ 의 개수가 $\frac{10^5}{x}$ 이니, 곱하면 $O(10^5 \times k)$ 가 된다. 이는 10번 실행해도 시간 제한에 문제가 없다.

Subtask 2 (21점)

이제 편의상 $N = 60$ 이라고 표현한다. ($k$ 라고 쓰지 않는 이유는, 둘이 조금 다르기 때문이다. 정확히는 $\log (\sum_{i=0}^{k-1} 2^i \times A[i]))$ 이다.)

$x = 1$ 인 경우로, 여러 명에게 나눠주는 것을 생각할 필요 없이 특정한 맛의 합을 이룰 수 있는 지만 보면 된다.

핵심적인 아이디어는 다음과 같다. 모든 비스킷의 맛이 $2^i$ 꼴이니, $y$ 를 작은 비트부터 차례로 맞춰나가보자. $y$ 의 0번째 비트를 0/1로 채우고, 그에 따라 0번 비스킷을 사용하자. 그 이후 1번째 비트 이상을 채울 때, 0번 종류 비스킷은 항상 2개, 4개, 6개 묶음으로 필요하게 된다. 이것은 1번 종류 비스킷을 1개, 2개, 3개 쓰는 것과 차이가 없고, 고로 0번 종류 비스킷 $X$ 개가 있으면 1번 종류 비스킷 $\lfloor \frac{X}{2} \rfloor$ 개로 바꿔서 생각할 수 있다. 이 논리는 1번 비스킷, 2번 비스킷에도 순서대로 적용할 수 있다.

이를 활용해서 재귀적으로 문제를 해결하자. $f(i, j)$ = ($y$ 의 $i \ldots 59$ 번 비트를 채우는 중이고, 전 단계에서 끌어온 $i$ 번 비스킷이 $j$ 개 있을 때 가능한 $y$ 의 경우의 수) 라고 하자. $i$ 번 비트를 0으로 두면 다음 상태는 $f(i + 1, \lfloor \frac{j + A[i]}{2} \rfloor)$ 이 되고, 1으로 두면 다음 상태는 $f(i + 1, \lfloor \frac{j + A[i] - 1}{2} \rfloor)$ 이 된다 (이 때 물론 $j + A[i] > 0$ 이어야 한다). 고로 간단한 재귀식을 유도할 수 있다.

이를 단순히 재귀함수로 구현하면 각 쿼리당 $O(2^{60})$ 이 소모된다. 하지만 각 상태마다 서로 다른 $j$ 가 많아야 2개 밖에 없음을 보일 수 있다. 자세히 말해서, $i$ 에 대응되는 $j$ 가 두 개일 경우 이는 항상 ${k, k + 1}$ 꼴을 이룬다. 이 경우, 다음 상태에서 가능한 수는 ${\frac{k-1+A[i]]}{2}, \frac{k+A[i]}{2}, \frac{k+1+A[i]}{2}}$ 뿐이고, $\frac{k-1+A[i]}{2} +1 = \frac{k+1+A[i]}{2}$ 이니, 계속 해당 꼴이 유지됨을 알 수 있다. 고로 메모이제이션을 추가해 주면, 상태의 개수가 $O(N)$ 정도가 된다. 고로 문제가 $O(N \log N)$ 에 해결된다.

Subtask 3 (42점)

$x > 1$ 이어도 사실 거의 동일한 풀이가 된다. 여기서는, $i$ 번 비트를 1으로 두면 다음 상태는 $f(i + 1, \lfloor \frac{j + A[i] - x}{2} \rfloor)$ 이 된다 (단 $j + A[i] \geq x$).

이렇게 했을 때 상태의 개수는 $O(Nx)$ 정도가 된다. 현재 상태에서 가능한 $j$ 의 최소와 최대의 차이가 최대 $x$ 로 유지되기 때문이다. 이유는 아까와 동일한 방식으로 보일 수 있는데, $f(i, *)$ 에서 가능한 $j$ 의 최소와 최대의 차이가 $x$ 이하이면, 최소에서 $x$ 를 빼면 차이가 $2x$ 가 되고, 다시 이를 2로 나누면 차이가 $x$ 가 되기 때문이다. 고로 메모이제이션을 하면 된다. 다만 이 경우 약간 효율적으로 구현해야 하는데, $(j, dp(i, j))$ 의 pair를 중복을 감안하여 관리하는 식으로 비재귀적으로 구현하거나, unordered_map 을 사용하는 정도면 괜찮을 것 같다.

만점 풀이

만점 풀이를 얻기 위해서는 위 서브태스크의 관찰을 발전시킨 후 완전히 다른 풀이를 유도해야 한다. 우리가 DP를 계산할 때 $j$에 하는 것은, 무언가를 더하고 2로 나누는 연산의 반복이다. 이 과정에서, $j$ 는 0 이상이 항상 유지되어야 한다. 우리는 이 조건을 만족하는 $y$ 의 개수를 세는 것이니, 이 조건을 다른 식으로 해석해 보자.

$x$ 를 빼는 상황을 고려하지 않았을 때, 위 연산이 음수에 도달하지 않을 조건은, 모든 $0 \le i \le k - 1$ 에 대해 $\sum_{j = 0}^{i}{2^j \times A[j]} \geq 0$ 이다. 이유는, 사실 수학적으로는 다음 상태를 $\lfloor \frac{j + A[i]}{2} \rfloor$ 와 같이 내림해서 구할 필요가 없이 그냥 $\frac{j + A[i]}{2}$ 로 그대로 써도 아무 차이가 없기 때문이다. 이렇게 되면 양변에 $2^{i}$ 를 곱하면 위와 같은 식을 유도할 수 있다.

우리는 각 $A[i]$ 항에서 $x$ 를 빼거나 안 뺄 수 있다. $A[i]$ 에 $x$ 를 빼었다면 $B[i] = 1$, 아니면 $B[i] = 0$ 이라고 하자. 이 경우 $B$ 는 그냥 $y$ 의 이진수 표현이다. 이렇게 하면:

$\sum_{j = 0}^{i} 2^j \times (A[j] - x B[j]) \geq 0$

$\frac{\sum_{j = 0}^{i} (2^j \times A[j])}{x} \geq \sum_{j = 0}^{i} (2^j \times B[j])$

$F[i] = \frac{\sum_{j = 0}^{i} (2^j \times A[j])}{x}$ 라고 정의하면, 우리의 조건은 $\sum_{j = 0}^{i} (2^j \times B[j]) \le F[i]$ 이다. 즉, $y$ 를 이진전개했을 때 suffix가 특정 수 이하여야 한다는 조건들이 있는 것이다.

이제 $y$ 를 큰 자리부터 맞춰 나가자 (작은 자리부터 맞춰 나가던 아까의 접근과 반대이다). $DP[i][j] = i+1$ 번 자리 이후를 모두 맞췄으며, $i$ 번 자리까지의 prefix가 $j$ 이하여야 할 때 올바른 $y$ 의 개수라고 하자. 답은 $DP[N-1][2^N - 1]$ 이 된다. 이 경우, $B[i] = 0$ 일 때 다음 상태 전이는 $DP[i-1][min({j, 2^i - 1, F[i]})]$ 가 되고, $B[i] = 1$ 일 때는 $DP[i-1][min({j - 2^i, 2^i - 1, F[i] - 2^i})] $ 와 같이 된다.

이렇게 될 경우 가능한 상태가 $O(2^N)$ 이 될 것이라고 생각할 수 있지만, 사실은 이보다 많이 작다. 한 $i$ 에 올 수 있는 $j$ 는, $2^{i+1} - 1$ 이거나, 어떠한 $F[j]$ ($j \geq i$) 의 길이 $i+1$ 의 suffix 뿐이다. 고로, 각 $i$ 에 대해서 가능한 $j$ 가 $O(N)$ 개고, 총 상태는 $O(N^2)$ 가 된다. 이제 이 DP를 메모이제이션을 사용한 백트래킹으로 구현하면 unordered_map 을 사용하여 $O(N^2)$ 정도의 시간 복잡도에 구현할 수 있다.

Problem 5. 버섯 세기

Problem

$n$ 개의 버섯이 있다. 각 버섯은 A 종류 거나 B 종류 이며 $0 \ldots n -1$ 까지 순서대로 번호가 붙어 있다. 0번 버섯은 A번 종류임이 보장된다.

당신은 이 $n$ 개의 버섯 중 몇 개의 버섯이 A 종류인지 세어야 한다. 하지만 당신은 버섯의 종류를 직접 알 수 없고, 기계를 사용해서 간접적으로 알아내야 한다. 기계에 당신은 $2$ 개 이상 $n$ 개 이하의 서로 다른 버섯들을 차례대로 넣어야 한다. 기계는 이들을 분석해서, 인접한 버섯 중 종류가 다른 버섯의 개수를 반환한다. 예를 들어, 넣은 버섯의 종류가 $[A, B, B, A]$ 라면, $A-B$ 는 다르고, $B-B$는 같고, $B - A$ 는 다르니, 2가 반환된다. 기계에 넣은 버섯 개수의 총 합은 10만개 이하여야 한다.

기계 사용 횟수 $Q$를 최소화하면서 버섯의 개수를 세자. 모든 서브태스크에 대해 $n \le 20000$이고, 만점을 받기 위해서는 $Q \le 226$ 이어야 한다.

Solution

원래 92.62점이 만점이었다가 대회 전날에 급하게 $Q = 226$ 풀이를 찾고 문제가 바뀌었다고 들었다. :)

1. $Q = 19999$ (10점)

0번 버섯이 A 종류이니, 기계에 $[0, i]$ 를 넣으면 $i$ 번 버섯의 종류를 바로 알 수 있다. 이를 $1 \ldots n - 1$ 에 대해 반복하면 된다.

2. $Q = 10000$ (25점)

위 방법을 약간만 개선하면 된다. 기계에 $[i, 0, i + 1]$ 을 넣으면, $i$ 번 버섯과 $i+1$ 버섯 중 B번 버섯인 것의 개수가 반환된다. 이를 $(1, 2), (3, 4), \ldots$ 에 대해서 다 해주자. $n$ 이 짝수면 마지막 원소는 따로 물어봐야 한다.

3. $Q = 282$ (80.14점)

226이라는 제한을 보면 sqrt decomposition 류의 풀이가 될 것이라고 예상하기 쉽다. 실제로도 $\log $ 근처의 쿼리로 이 문제를 푸는 것은 매우 어려워 보이니, sqrt decomposition에 기반한 풀이를 생각해 보자.

핵심 아이디어는, $A$ 가 $x$ 개 있으면, $x$ 개의 버섯 중 $A$ 종류 버섯의 개수를 알 수 있다는 것이다. 다음과 같은 식으로 배치하면 된다:

AXAXAXAXAXAXAXAY

이 때 $A$ 는 우리가 A 종류임을 확실히 아는 버섯들이고, $X, Y$ 는 우리가 알고 싶은 버섯들이다. 이렇게 되면, 기계의 반환 결과는 2 * ($X$ 에 있는 B 종류 버섯) + ($Y$ 에 있는 B 종류 버섯) 이 된다. 이 결과를 통해서, 우리는 XXXXXY 형태로 넣은 버섯 중 A 종류 버섯의 개수를 계산할 수 있다. 같은 이유로, $B$ 가 $x$ 개 있어도 $x$ 개의 버섯 중 $A$ 종류 버섯의 개수를 알 수 있다. 고로 필요한 것은

• A와 B를 합해서 $2X$ 개 쌓는 것
• $X$ 개 이상인 A 혹은 B를 사용해서, $\frac{N}{X}$ 번 만에 나머지 원소들의 개수를 세는 것

첫 번째 작업은 $X$ 번의 연산으로 가능하다. 2번의 쿼리로 ${0, 1, 2}$ 번 원소 중 무엇이 A이고 무엇이 B인지를 확인하자. 특정 종류의 원소가 2개 이상, 예를 들어 A가 2개 이상 있다면, AxAy 의 형태로 질문을 한다면 결과가 ${0, 1, 2, 3}$ 으로 나오고, 그 결과에 따라서 $x, y$ 의 종류를 알 수 있다. 이러한 방법으로 2개의 원소의 종류를 알 수 있다.

결론적으로 $X + \frac{N}{X}$ 번의 연산이 필요하며, $X = \sqrt N$ 으로 잡으면 282번 정도의 연산이 필요하다. 이 때, $N \le 400$ 이라면 edge case가 발생할 수 있으니, 25점 서브태스크의 방법을 따로 구현하여 쓰는 것이 편하다.

4. $Q = 244$ (92.62점)

AXAXAXAXAXAXAXAY 와 같은 배치를 쿼리했을 때 개수 말고 얻을 수 있는 정보가 딱 하나 더 있는데, 바로 맨 뒤에 있는 $Y$ 버섯의 종류이다. 고로, $N/X$ 번의 연산 과정에서 A 종류 버섯의 개수를 셀 뿐만 아니라, 세는 틀의 길이를 조금씩 늘려나갈 수 있다.

이렇게 하면 $X$ 를 어떻게 설정해야지 최소 횟수의 쿼리를 얻을 수 있을까? 나의 경우에는 각 $X$ 의 선택마다 필요한 연산의 횟수를 계산하는 프로그램을 따로 작성해서 적당한 $X$ 를 구했다. $X = 79$ 로 설정하면, $Q = 244$ 가 나오는 것이 내가 찾을 수 있는 최소였다. 이를 구현하면 92.62점이 나온다.

5. $Q \le 226$ (100점)

80점 풀이에서 언급했듯이 지금의 풀이는 처음에 A, B를 $2X$ 개 쌓는 단계와 $X$ 개 이상인 A 혹은 B로 나머지를 빠르게 구하는 단계로 분리되어 있다. 92.62점 풀이에서는 이 중 두 번째 단계를 최적화했는데, 아래에 나오는 풀이들은 모두 첫 번째 단계를 최적화한다.

정해로 의도된 풀이는 A, B를 쌓는 단계를 약간 더 최적화한다. 현재의 풀이는 한 번의 쿼리로 2개의 버섯의 종류를 얻어내는데, 이 대신 두 번의 쿼리로 5개의 버섯의 종류를 알아낼 수 있다는 것이다. 이 규칙 자체는 사람이 직접 분석하기에는 케이스가 너무 많아서, Decision tree를 전부 brute-force해 보는 방법으로, 노가다를 기계로 대신하여 찾는다. 이 풀이에 대해서는 전명우님의 블로그에 코드와 함께 잘 설명이 되어 있다. 이 풀이를 사용할 경우 정확히 $226$ 개의 쿼리를 사용하여 만점을 얻을 수 있다. 아래에서 이와 다른, 조금 더 적은 쿼리를 사용하는 풀이를 설명할 것이라 이 풀이는 짧게만 언급한다.

6. $Q \le 209$ (100점)

A, B를 쌓는 단계를 많이 최적화하는 풀이를 소개한다. 약간이 아니라 많이인 이유는, 정해에서는 한 번의 쿼리가 평균적으로 상수 개의 버섯의 종류를 찾지만, 여기서는 한 번의 쿼리가 평균적으로 $O(\log N)$ 개의 버섯의 종류를 찾기 때문이다. 실제로는 Big O 뒤에 숨겨진 상수로 인해 아주 기적적인 성능 향상이 있지는 않으나, 의도된 풀이보다는 쿼리 개수가 유의미하게 적은 편이다. 또한, 한 번의 쿼리를 통해서 알아낼 수 있는 정보의 수가 $\log_2 N$ 비트이니, 모든 버섯의 종류를 구해야 한다는 가정 안에서 이 풀이는 asymptotically optimal하다.

기본 틀은 다음과 같다. 우리가 현재 $X$ 개의 A 혹은 B를 가지고 있다고 하자. 한 번의 쿼리를 통해서, 우리는 한 원소의 값을 정확히 알 수 있으며, 나머지 원소들의 값의 합 역시 알 수 있다. 첫 번째를 잠시 무시하면, 우리는 인터랙터에게 어떠한 버섯 집합 $S$ 를 줄 수 있고 ($|S| \le X$), 인터랙터는 집합에 있는 버섯 중 $B$ 의 개수를 반환할 것이다. 여기서 목표는, 쿼리를 $O(N / \log N)$ 번 이하로 하면서 모든 버섯의 종류를 얻어내는 것이다. 이것이 어떻게 말이 되나 싶지만, 놀랍게도 가능하다는 것을 아래 보인다.

6.1 $O(N / \log N)$ 번의 쿼리로 이진 수열 복원하기

아래 내용은 상당 부분 이 글과 이 코드를 참고했다.

문제를 조금 더 간단화해서, 인터랙터에게 줄 수 있는 버섯 집합의 크기 제한을 없애 보자 (즉 $S$의 크기가 아주 커도 무방하다). 우리는 0과 1로 이뤄진 크기 $N$ 의 배열 $b_0, b_1, \ldots, b_{N - 1}$ 이 있을 때, 원하는 부분집합의 원소 합 $\sum_{i \in S} b_i$ 를 $O(N / \log N)$ 번의 쿼리로 물어본 이후 배열의 모든 원소를 찾을 것이다.

이를 해결하기 위해 분할 정복과 비슷한 방법을 사용한다. $f_k$ 를, $2^k$ 개의 쿼리로 우리의 전략이 값을 얻을 수 있는 원소 수라고 하자. $f_0 = 1$, $f_{k + 1} = 2f_k + 2^k - 1$ 인 전략을 소개한다.

먼저, $k = 0$ 인 경우에는, ${0}$ 집합에 대해서 물어보면 $1$ 개의 원소에 대한 답을 구할 수 있다.

그렇지 않은 경우, 현재 배열의 크기가 $N = f_{k+1} = 2f_k + 2^k - 1$ 이라고 하자. $S_{k_1}$ 를, $[0, f_k)$ 구간에 대한 값을 구하는 쿼리 집합, $S_{k_2}$ 를, $[f_k, 2f_k)$ 구간에 대한 값을 구하는 쿼리 집합이라고 하자. 물론 이 두 집합은 하술할 방법을 그대로 사용하여 재귀적으로 만든 것이다. 이 두 집합을 토대로 크기 $k + 1$ 의 쿼리 집합 $S$ 를 다음과 같이 구성한다. $S[i]$ 를 쿼리 집합의 $i$ ($0 \le i < |S|$) 번째 원소라 할 때

• $S[0] = [f_k, 2f_k)$.
• 모든 $0 \le i < 2^k - 1$ 에 대해,
  • $S[2i + 1] = S_{k_1}[i] \cup S_{k_2}[i]$
  • $S[2i + 2] = S_{k_1}[i] \cup ([f_k, 2f_k) \setminus S_{k_2}[i]) \cup {2 f_k + i}$
• $S[2^{k+1} - 1] = [0, f_{k+1})$

이제 이러한 쿼리 집합이 있을 때 어떻게 전체 값을 구하는지 살펴보자. $v[i]$ 를 $S[i]$ 에 있는 $b_i$의 합이라고 정의하고, $v_{k_1}, v_{k_2}$ 역시 $S_{k_1}, S_{k_2}$ 에 대해 유사하게 정의하자. 먼저, 모든 $0 \le i < 2^k - 1$ 에 대해,

• $v[2i+1] = v_{k_1}[i] + v_{k_2}[i]$
• $v[2i+2] - v[0] = v_{k_1}[i]- v_{k_2}[i] + b_{2f_k + i}$

모든 원소가 정수이고, $b_{2f_k + i}$ 는 $0$ 이거나 $1$ 이기 때문에, 이것을 토대로 $v_{k_1}[i], v_{k_2}[i], b_{2f_k + i}$ 의 값을 모두 유일하게 결정할 수 있다. $[2f_k, f_{k+1})$ 구간에 대해서 값을 결정했으니, 이제 $v_{k_1}[2^k-1], v_{k_2}[2^k-1]$ 만 알아낸다면, 귀납적으로 $[0, f_k), [f_k, 2f_k)$ 구간에 대해서도 답을 구할 수 있다. 이 때

• $v_{k_2}[2^k - 1] = S[0]$
• $v_{k_1}[2^k - 1] = S[2^{k+1} - 1] - S[0] - \sum_{i = 0}^{2^k - 1} b_{2f_k + i}$

이다. 고로 간단화한 문제를 해결할 수 있다.

6.2. 원래 문제로 돌아오기

원래 문제가 우리가 간단화한 문제와 다른 점은

• 물어볼 수 있는 쿼리 집합의 크기가, 현재 답을 알아낸 원소 크기보다 작아야 한다
• 매 쿼리마다 한 원소의 값을 추가적으로 알아낼 수 있다

이다. 이 제약 조건을 염두에 두고 위에서 구성한 $\log N$ 개의 쿼리 집합을 잘 활용해 보자. 한 가지 활용할 수 있는 것은, 한 쿼리 집합 안에서 쿼리를 물어보는 순서는 상관 없다. 쿼리의 결과만 있으면 모든 답을 역산할 수 있기 때문이다. 한 집합 상의 쿼리를 물어보는 원소의 개수 순으로 정렬한 후 사용한다면, 매 쿼리마다 답을 알아낸 원소 크기가 증가한다는 성질을 활용하여 초기 집합의 크기가 작을 때도 효율적으로 쿼리를 물어볼 수 있다. 이렇게 정렬을 할 경우, 각 쿼리 집합을 활용하기 전에 알아야 할 원소 수의 최댓값을 최소화할 수 있다.

이제 각 쿼리 집합을 활용하는 것을 일종의 냅색으로 생각할 수 있다. 각 쿼리 집합에 대해서, 해당 집합을 사용하기 전에 필요한 원소 수가 얼마인지를 계산해 줄 수 있다. 이 쿼리 집합을 고르면, 특정 개수의 쿼리를 사용해서 원소 수를 늘려준다.

$DP[n]$ 을 $n$ 번의 쿼리로 얻을 수 있는 최대 원소 수라고 정의하고, 위 $\log N$ 개의 쿼리 집합을 사용하여 DP의 최댓값을 구해주자. 모든 $0 \le i$ 에 대해서, $i$ 번의 쿼리를 사용해서 최대한 많은 버섯의 결과를 결정한 후, 그 결과를 가지고 남은 버섯을 한꺼번에 결정하는 것을 반복했을 때, $N$ 개의 버섯을 얻는 데 드는 최소 시간을 계산하자. 이 시간을 최소화하는 $i$ 를 찾은 후, DP를 역추적한다. 역추적한 결과를 토대로 $2^k$ 크기의 쿼리 집합을 사용하여 초기 값을 불린 후, 초기 값을 토대로 92.62점 풀이와 같이 전체 집합을 $N$ 으로 늘려주면 된다.

위 알고리즘이 쿼리 수를 얼마나 최소화하는지는 돌려 봐야만 알 수 있는데, 본인의 계산으로는 최대 $209$ 번의 쿼리 안에 문제를 해결할 수 있다.

7. $Q \le 203$ (100점)

$2^k$ 크기의 쿼리 집합을 사용하여 문제를 해결할 때, 각 쿼리 집합이 충분히 작음을 보장할 수 있다면 집합의 가용 범위가 높아져서 더 효율적일 것이다. 이 크기를 엄청나게 줄이지는 못해도, 최소한 가장 큰 집합인 $S[2^k - 1]$ 의 크기는 줄여줄 수 있다. 전체집합이니, $S[2^k - 1] \setminus S[2^k - 2]$ 을 대신 물어본 후 합치면 되기 때문이다. 이 최적화를 하면 쿼리가 $6$번 줄어서 $203$ 번의 쿼리 안에 문제를 해결할 수 있다.

Problem 6. 기지국

Problem

이 문제는 Two steps 타입으로, 기존 IOI에 나왔던 Saveit이나 Last Supper와 유사한 형태의 문제이다.

트리 $T$ 가 있고, 다음과 같은 쿼리를 지원해야 한다.

• 서로 다른 두 정점 $s, t$ 가 주어질 때, $s$ 에서 인접한 정점 중 $t$에 더 가까워지는 정점은 유일하다. 이 정점을 반환하라.

당신은 이 쿼리를 지원하기 위해서 다음과 같은 두 프로그램을 작성해야 한다.

• label 프로그램에는 입력으로 트리 $T$ 가 주어진다. label 프로그램은 $T$ 에 있는 모든 정점들에 대해서 서로 다른 라벨 을 배정해야 한다. 라벨은 $[0, k]$ 사이에 속하는 정수여야 하고, $k$ 는 입력으로 주어진다: 만점을 받기 위해서는 라벨로 적힌 정수의 최댓값을 최소화해야 한다.
• station 프로그램에는 입력으로 두 정점 $s, t$ 의 라벨, 그리고 $s$ 에 인접한 정점들의 라벨이 주어진다. 두 정점의 절대 번호가 아니라, label 프로그램에서 당신이 배정한 라벨이 주어지는 것이다. 이 때 라벨은 모두 오름차순으로 주어진다. 당신은 $t$ 에 더 가까워지는 유일한 정점의 라벨을 반환해야 한다.

Solution

잡다한 서브태스크 (39점)

서브태스크 1-4는 만점 풀이에 도움이 전혀 안 되는 것 같다. 고로 짧게만 언급한다.

• Subtask 1: 선을 따라서 $0, 1, \ldots, n-1$ 을 순서대로 붙여주면, $s < t$ 일 경우 $s+1$, 아니면 $s-1$ 을 반환하면 된다.
• Subtask 2: 트리 형태가 고정되어 있으니, 그냥 $label[i] = i$ 로 두고 station 프로그램에서는 직접 찾아보면 된다.
• Subtask 3: 최대 차수의 정점을 루트로 잡자. (깊이, 루트에서 무슨 서브트리에 속하는지) 쌍을 보내주면 된다. 정수 하나가 아니라 pair를 라벨링하는 것은, 1000*(깊이) + (서브트리 인덱스) 를 적어주면 된다. $k \geq n^2$ 라 괜찮다.
• Subtask 4: 해당 정점의 라벨과, 해당 정점에 인접한 모든 정점과의 거리 리스트를 보내주면 된다. 정점 $v$ 면, $(v, dist(v, 0), dist(v, 1), \ldots, dist(v, n-1))$ 과 같이 보내주면 된다. 적당히 십진수로 인코딩하면 된다.

$k = n^2$ (65.32점)

Interactive 형태가 아니라, 일반적인 상황에서 위 문제를 해결한다고 하자. $s$ 가 $t$ 의 조상 중 하나라면, 결국 $t$ 가 속한 서브트리가 무엇인지를 찾는 문제가 된다. 서브트리에 대한 질문이니, DFS ordering을 동반하면 좋을 것이다. 특히 DFS ordering은 각 정점에 들어간 시간, 그리고 나간 시간만 기록해도 서브트리에 속하는지 여부를 판별할 수 있다. 한정된 정보량을 가진 우리의 상황에 매우 적합하다. 이 글에서는 DFS preorder, DFS ordering에 대해서는 설명하지 않으니 궁금하다면 따로 찾아보자.

label 함수에서는, 트리의 0번 정점을 루트로 한 후, 각 노드에 대해서 $(din[v], dout[v])$ 를 배정해서 주자. ($din[v] \times 1000 + dout[v]$ 를 저장하면 된다.) 이때 $din[v]$ 는 해당 정점에 DFS preorder로 들어간 시간, $dout[v]$ 는 해당 정점에 DFS preorder로 나간 시간이다. 이제 $w$ 가 $v$ 의 서브트리라는 것은 $din[v] \le din[w]$, $dout[w] \le dout[v]$ 라는 두 조건이 성립한다는 것과 동치이다.

이제 각 쿼리에 대해서 $s, t$, 그리고 $s$ 에 인접한 정점의 $(din[v], dout[v])$ 정보를 알 수 있다. 이제 이 정점들에 대해서, 누가 누구의 서브트리에 속하는지를 알 수 있다. 고로

• $s$ 의 서브트리에 $t$ 가 없다면, $s$ 를 서브트리로 가지는 부모 정점을 반환.
• 있다면, $t$ 를 서브트리로 가지는 자식 정점을 찾아 반환.

이렇게 하면 65점을 받는다. $din[v] \le dout[v]$ 라는 점을 활용해 $k = n(n+1)/2$ 로 줄이는 등의 더러운 최적화가 가능하긴 할 텐데 의미가 있는 지는 모르겠다.

$k = n$ (100점)

사실 많은 경우에는 $din[v]$ 나 $dout[v]$ 중 하나만 필요하다. 예를 들어서, $s$ 의 서브트리에 $t$ 가 있어서, 이것이 어느 쪽 서브트리인지를 확인해야 한다고 하자. 이 때 자식에 있는 노드들이 $v_1, v_2, \ldots, v_k$ 라고 할 때, $dout[v_i] + 1 = din[v_{i + 1}]$ 이 만족된다. 즉 시작점만 알아도 보통 끝 점을 알 수 있다는 것이다. 또한, $dout[v_k] = dout[s]$ 이다. 고로 자식 노드들에 대해서 $din[v]$ 를 알고, 자신에 대해서는 $dout[v]$ 만 알면 웬만하면 파악이 된다는 것이다. 대략 비슷한 이유도 반대도 성립한다.

트리는 이분 그래프이다. 트리의 노드들 중에서 짝수 깊이에 있는 노드들에는 $din[v]$, 홀수 깊이에 있는 노드들에게는 $dout[v]$ 를 매겨주자. 이 때 서로 같은 값이 배정될 수 있기 때문에, $dout[v]$를 구해줄 때도 인덱스를 늘려주는 식으로 구현하자. 이렇게 되면 $din[v], dout[v]$ 에 $[0, 2n-1]$ 사이의 서로 다른 값이 배정된다.

이제 이것만으로도 문제에서 물어보는 쿼리에 대답하기 충분함을 보인다. $s$ 의 깊이에 따라서 케이스를 나누자. 편의상, $s$ 의 차수가 2 이상이라고 가정하고 (1이면 그냥 $c[0]$ 을 반환하면 되니 자명하다), $s$ 가 루트가 아니라고 가정하자 (적절한 예외처리를 하면 되고, 사실 위 알고리즘 특성상 딱히 예외처리를 안 하더라도 잘 된다).

• $s$ 가 짝수 깊이에 있다면, 모든 인접한 노드들의 라벨은 $s$ 보다 크다. 또한 라벨이 가장 큰 노드는 부모 노드이다. 각 서브트리의 구간은 $[label[s] + 1, label[c_0]], [label[c_0] + 1, label[c_1]], \ldots$ 와 같다. 이 중 속하는 게 있으면 대응되는 라벨을 반환하고, 아니면 최댓값 (부모) 를 반환한다.
• $s$ 가 홀수 깊이에 있다면, 모든 인접한 노드들의 라벨은 $s$ 보다 작다. 또한 라벨이 가장 작은 노드는 부모 노드이다. 각 서브트리의 구간은 $[label[c_1], label[c_2] - 1], [label[c_2], label[c_3] - 1], \ldots, [label[c_{k-1}], label[s] - 1]$ 와 같다. 이 중 속하는 게 있으면 대응되는 라벨을 반환하고, 아니면 최솟값 (부모) 를 반환한다.

마지막으로, 홀수 깊이에 있는 노드들의 $din[v]$ 나 짝수 깊이에 있는 노드들의 $dout[v]$ 는 아무도 신경쓰지 않기 때문에 방문하면서 기록할 필요도 없고, 인덱스를 늘려줄 필요도 없다. 고로 이 값들을 단순히 무시해주면 $[0, n - 1]$ 사이의 서로 다른 값을 배정하고 문제를 해결할 수 있다.