티스토리 뷰

공부

IOI 2020 Day 2

구사과 2020. 9. 24. 23:47

(9/29 01:20 - 4번 문제 풀이가 추가되었다.)

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$ 풀이를 찾고 문제가 바뀌었다고 들었다. :)

$Q = 19999$ (10점)

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

$Q = 10000$ (25점)

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

$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점 서브태스크의 방법을 따로 구현하여 쓰는 것이 편하다.

$Q = 245$ (92.62점)

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

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

$Q = 226$ (100점)

작성중입니다.

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]$ 사이의 서로 다른 값을 배정하고 문제를 해결할 수 있다.

'공부' 카테고리의 다른 글

2020 ICPC 서울 인터넷 예선  (3) 2020.10.10
IOI 2020 Day 2  (0) 2020.09.24
IOI 2020 Day 1  (0) 2020.09.23
APIO 2020  (1) 2020.08.25
일반 매칭과 응용  (2) 2020.08.22
20200814 problem solving  (0) 2020.08.14
댓글
댓글쓰기 폼
공지사항
Total
467,062
Today
0
Yesterday
508