IOI 2022 Day 2

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

• 장태환, 100 / 53 / 58 / 100 / 93.05 / 55, 459.05점, 22등 (금메달)
• 조영욱, 67 / 51.5 / 58 / 100 / 99.78 / 55, 431.28점, 26등 (금메달)
• 반딧불, 53 / 80 / 58 / 34 / 100 / 55, 380.00점, 38등 (은메달)
• 박상훈, 70 / 72 / 27 / 34 / 96.10 / 55, 354.10점, 42등 (은메달)

한국 학생들은 금메달 2개, 은메달 2개로 평균 이상의 성적을 거두었다. 전반적으로 금메달 컷 근처에서 점수가 형성되어 있어서, 조금만 잘 했으면 하는 아쉬움이 남기도 한다. 장태환 학생은 작년 첫 출전에서 동메달을 땄었는데, 올해는 선발고사 / APIO 모두에서 멋진 성적을 내고 많은 기대를 받았으며, 기대에 부응하는 금메달을 거머쥐었다. 축하합니다! 그 외에도, 올해 역시 힘든 환경에서 열심히 교육 진행해준 학생들에게 감사를 전한다.

올해의 우승자는 모든 문제를 해결한 중국의 Jiangqi Dai, Shaoxuan Tang 학생으로, 작년과 동일하게 이번 대회에서 중국 학생들이 1/2/3/4등을 차지하였다. Jiangqi Dai 학생의 경우 현재 코드포스 세계 5등이고 이미 대회 3년 전부터 LGM 레이팅을 보유하고 있었다. 작년의 Mingyang Deng처럼 충분히 만점을 기대할 만한 학생이라고 생각한다. 5등은 미국의 Hankai Zhang, 6등은 캐나다의 Zixiang Zhou, 7등은 우크라이나의 Roman Yanushevskyi가 차지하였다. 축하합니다!

Day 2 Problems PDF

notice-en_ISC.pdf

0.15MB

notice-ko_KR.pdf

0.23MB

circuit-en_ISC.pdf

0.20MB

circuit-ko_KR.pdf

0.32MB

insects-en_ISC.pdf

0.17MB

insects-ko_KR.pdf

0.33MB

islands-en_ISC.pdf

0.20MB

islands-ko_KR.pdf

0.31MB

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

문제 4. 디지털 회로

서브태스크 3 (18점)

쿼리를 무시하고, 게이트들의 배정만 있을 때 문제를 해결하는 법을 살펴보자.

이 문제의 Naive한 풀이는 그다지 간단하지 않은 트리 DP이다. $DP[v]$ 를, $v$ 번 게이트의 서브트리 안의 모든 파라미터 조정 경우 중, $1$ 을 반환하는 경우의 수라고 하고, $Sum[v]$ 를, $v$ 번 게이트의 서브트리 안의 모든 파라미터 조정 경우라고 하자. $deg(v)$ 를, $v$ 번 게이트의 자식의 수라고 하자.

$Sum[v]$ 는, $v$ 번 게이트의 서브트리의 $deg(v)$ 곱으로, 쉽게 $O(N)$ 에 계산할 수 있다.

$DP[v]$ 의 경우는 단순하게 되지 않고 추가적인 DP를 해야 한다. 자식에 대한 DP 값이 모두 계산되었다고 하자. 각 노드 $v$ 에 대해서, $i$ 번 자식 $ch_v(i)$ 가 $0$ 을 반환하는 경우의 수는 $a_i = Sum[ch_v(i)] - DP[ch_v(i)]$, $1$ 을 반환하는 경우의 수는 $b_i = DP[ch_v(i)]$ 이다. 이를 토대로 $DPC[i][j]$ 를, 맨 앞 $i$ 개의 자식 중 $j$ 개의 게이트가 $1$ 을 반환하는 경우의 수라고 정의하면:

$DPC[i][j] = DPC[i - 1][j] \times a_i + DPC[i - 1][j - 1] \times b_i$

이고, 결론적으로 $DP[v] = \sum_{i = 0}^{deg(v)}(DPC[deg(v)][i] \times i)$ 이다.

모든 노드에 대해서 $DP[v]$ 값은 $deg(v)^2$ 시간에 계산되기 때문에, 총 $O((N + M)^2)$ 시간에 각 쿼리가 해결되고, 이를 합산하면 $O(Q (N + M)^2)$ 의 알고리즘을 얻는다.

만점 풀이

서브태스크들이 굉장히 많지만 이 중 도움이 되는 서브태스크는 전혀 없다고 봐도 무방하다. 34점까지는 긁는 것이 간단한 편이지만, 그 이후는 긁기도 쉽지 않으며 이는 스코어보드로도 확인할 수 있다.

서브태스크로는 없으나, 각각의 쿼리에 대해서 선형 시간에 해결하는 풀이에 대해서 고민해 보는 것이 필요하다. 상식적으로 봤을 때, 하나의 쿼리에 대해서 선형 시간에 해결하지 못하면서 여러 쿼리는 준 선형으로 해결할 수 있는 방법이 있을 것이라고 생각할 수는 없기 때문이다. 고로 먼저 $O(Q(N + M))$ 풀이를 설명한다.

목표는 $DPC[i][j]$를 계산하지 않으면서 답을 얻는 것이다. 사실, $\sum_{i = 0}^{deg(v)} DPC[deg(v)][i]$ 는 계산이 아주 쉬운데, 그냥 $\prod_{i = 1}^{deg(v)} (a_i + b_i) = \prod_{i = 1}^{deg(v)} Sum[ch_v(i)]$ 이기 때문이다. 비슷한 식으로, $\sum_{i = 0}^{deg(v)} DPC[deg(v)][i] \times i$ 역시 무언가 쉽게 쓸 수 있지 않을까? $ans_i = \sum_{j = 0}^{i} DPC[i][j] \times j$ 라고 하자. 이 때:

$ans_i = \sum_{j = 0}^{i} DPC[i][j] \times j$
$ans_i = \sum_{j = 0}^{i} (a_i DPC[i-1][j] + b_i DPC[i-1][j-1]) \times j$
$ans_i = a_i ans_{i - 1} + \sum_{j = 0}^{i} b_i DPC[i-1][j-1] \times (j - 1 + 1)$
$ans_i = (a_i + b_i) ans_{i - 1} + \sum_{j = 0}^{i} b_i DPC[i-1][j-1]$
$ans_i = (a_i + b_i) ans_{i - 1} + b_i \prod_{j = 1}^{i - 1} (a_j + b_j)$

이라는 식이 나온다. 이 식 자체로도 이미 선형 시간에 계산이 가능하다. 하지만 꼴이 너무 단순하여서, 더 정리할 수 있지 않을까 하는 생각이 든다. 실제로도, 더 정리해보면:

$ans_i = \sum_{j = 1}^{i} (\prod_{k \neq j} (a_k + b_k)) \times b_j$

라는 식이 나온다. (정말 여담인데, $a$ 를 계수로 가지는 생성함수를 $P$ 라고 할 때, $\sum (a_j \times j)$ 는 $P^\prime(1)$ 이라는 점을 활용하면, 이 식을 별다른 아이디어 없이 도출할 수 있다. 그냥 그렇다고...)

여기서 더 줄일 수도 있다. $(a_k + b_k)$ 는 쿼리 등등으로 바뀔 수 없는 고정된 상수이다. 고로, $dp_v = \sum{C_i \times dp_{ch_v(i)}}$ 와 같이, 자식의 DP 값에 어떠한 상수를 곱해준 것으로 볼 수 있다. 달리 말해, 모든 $dp_v = 1$ 인 리프에 대해서, 해당 리프가 $dp_0$ 에 기여하는 바는 고정된 상수라는 것이다. 즉 이 고정된 상수를 알면, 켜져있는 리프에 대해서 이 값만 더해주면 된다.

계산을 해 보면, 각 리프에 대해서, 리프 - 루트로 올라가는 경로에 없는 노드들에 대한 $deg(v)$ 의 곱이 전체 답임을 알 수 있다. 이 값은 Naive하게는 $O((N+M)^2)$ 에 계산할 수 있는데, Modular inverse가 안 되기 때문에 최적화가 조금 귀찮아진다. 크게 두 가지 해결 방법이 있다:

• 값을 대입하고, 전체 곱을 계산할 수 있는 세그먼트 트리를 만들어 준 후, DFS로 트리를 순회하면서, 현재 루트 방향에 있는 원소들에만 $1$ 을 대입한 후, 리프에서 세그먼트 트리에 쿼리를 한다. 코드는 좀 긴데 생각이나 설명이 제일 간단한 것 같다.
• $Coeff[v]$ 를 $v$ 의 서브트리와 루트 방향 경로를 뺀 모든 노드들의 $deg(x)$ 곱이라고 하자. $Coeff[v]$ 값을 통해서 모든 자식 $w \in ch(v)$ 에 대해 $Coeff[w]$ 값을 계산해 줄 수 있다. 해당 자식이 아닌 방향의 $Sum(v)$ 를 모두 곱해서 넣어주면 되는데, 이는 prefix/suffix 곱을 관리해 주면 되기 때문이다.

이제 각각의 쿼리에 대해서는 단순히 켜진 리프들에 대해서 위 값의 합을 반환하면 된다.

이 정도로 문제가 단순해진 이후에는 최적화도 상대적으로 간단하다. 리프들에 대해서, Lazy propagation을 사용한 세그먼트 트리를 구성하자. 각 노드에 대해서

• 현재 서브트리의 켜진 노드들의 값 합
• 현재 서브트리의 꺼진 노드들의 값 합

을 관리할 수 있다. 고로 각 쿼리가 $O(\log M)$ 에 처리되며, 시간 복잡도는 초기 전처리를 세그트리로 했다는 가정 하에 $O((N + M + Q) \log M)$ 이다.

문제 5. 드문 곤충

서브태스크 1 (10점)

모든 $0 \le i \le N - 1$ 번 곤충에 대해서, 이 곤충과 같은 번호를 가진 곤충 $j$ 의 리스트를 얻을 수 있다. $i$ 번 곤충을 넣고, 모든 다른 곤충을 한 번씩 넣어본 후, press_button 함수의 반환값이 들어있는 곤충의 개수와 일치하지 않으면 다시 빼주고, 그렇지 않을 때만 그대로 넣어주자. 이렇게 하면, 최종적으로 기계 안에 있는 곤충들이, $i$ 번 곤충과 종류가 같은 곤충 집합과 일치한다. 모든 함수가 정확히 $N^2$ 번 호출되어 10점을 얻을 수 있다.

$m \le 12$ (47.5점)

맨 처음, 서로 다른 곤충들의 개수를 얻을 수 있는 방법이 있다. 모든 곤충을 순서대로 넣어보는데, 만약에 press_button 함수의 반환값이 $2$ 이상이 될 경우 곤충을 다시 빼는 것이다. 이 경우 기계에 들어있는 곤충들은 모두 서로 다르며, 이 조건을 만족하는 최대 개수의 곤충이 들어 있다. 이 방법은 모든 연산을 최대 $N$번 호출한다. 이렇게 구한 서로 다른 곤충의 개수를 $D$ 라고 하자.

이를 일반화하여, 같은 종류의 곤충이 $x$개 이하인 최대 크기의 집합을 얻을 수도 있다. 위와 동일하게 하는데, 반환값이 $x + 1$ 이상일 때 곤충을 다시 빼는 것이다.

만약 문제의 정답이 $T$ 라면, $x \le T$ 에 대해서 이러한 최대 크기 집합은 $Dx$ 가 되고, $x > T$ 에 대해서 이러한 최대 크기 집합은 $Dx$ 미만이 된다. 이 점을 사용하면, 답에 대해 이분 탐색을 할 수 있고, 이 때의 복잡도는 $O(N \log N)$ 이다.

$m \le 3.033$ (99.89점)

여기서 최적화 두 개를 넣으면 99.89점을 얻을 수 있다. 대회장에서는 사실상 만점이라고 판단해도 충분할 만큼 좋은 풀이이다.

답을 $[1, N/D]$ 범위에서 이분 탐색하는데, 각 결정 문제가 참이거나 거짓일 때 다음과 같은 방법으로 후보를 줄인다.

• 만약 결정 문제가 참이 나왔다면, 현재 기계에 들어있는 후보를 이후 이분 탐색에서 제거할 이유가 없다.
• 만약 결정 문제가 거짓이 나왔다면, 현재 기계에 들어있지 않은 후보를 이후 이분탐색에서 삽입할 이유가 없다.

같은 이유로, 초기 $D$ 를 구할 때 기계에 넣어준 곤충들도 이후 작업에서 지워줄 필요가 없다. 이를 구현할 경우, 본인의 경우 99.89점을 얻을 수 있었다.

이 알고리즘은 굉장히 효율적인 것이, 매 이분 탐색 과정에서 기계에 들어있을 수도, 없을 수도 있는 곤충 후보들이 거의 반으로 줄어들기 때문이다. 초기에 기계에 있을 수도, 없을 수도 있는 곤충 후보는 $N - D$ 개이다. 이후 첫 이분 탐색에서 이러한 미정의 곤충들을 집합에 넣어볼 것인데, 이분 탐색의 결과에 따라 이 중 거의 절반의 후보들이 이후 기계에 절대 다시 들어가지 않거나 영원히 기계에 있게 된다. 이렇게 미정의 후보가 절반이 되는 것은 이후 연산에서도 반복되고, 결국 $N + N / 2 + N / 4 + \ldots \le 2N$ 이기 때문에 대략 $3N$ 번의 쿼리를 사용한다.

그럼에도 불구하고 이 풀이가 만점이 나오지 않는 이유는, 곤충 후보가 거의 반으로 주는 것이지 정확히 반으로 주는 것이 아니기 때문이다. 정확히 말해, 이분 탐색 과정에서 현재 $X$ 개의 곤충들이 미정인 상태라면, 이후 연산에서 미정인 곤충들은 $X/2$ 가 아닌 $(X + D) / 2$ 이하로 줄어들어 이 부분에서 오차가 발생한다.

다만, 이러한 오차를 극대화시키려면 $D$ 가 $N$ 근처일만큼 커야 하는데, 그러한 경우에는 또 이분 탐색 횟수 자체가 작은 등의 이유로 잘 통과가 된다. 이 댓글 에 따르면, error term을 정확히 계산했을 때 $(\log_2(\lceil N / D \rceil) - 4)D$ 정도가 나온다고 한다. 식을 계산하면 이 값은 $D = N / 16e$ 정도에서 최대가 나오고, 그 때의 값은 $\frac{1}{16e \ln(2)}N = 0.03317... \times N$ 정도이고, 점수로 환산하면 99.86점이다. Ceiling function을 무시한 것이라 아주 정확한 계산은 아니지만, 하여튼 데이터의 약함과 무관하게 만점에 준하는 풀이인 것이 사실이다.

만점 풀이?

사실 99.89 점으로도 충분히 좋은 풀이라서, 모든 문제를 풀지 않은 이상 굳이 대회장에서 시도해 볼 필요가 있나 싶기는 하다.

$3N$ 이하의 쿼리 수가 보장된 풀이는 현 시점에서 공식 풀이 및 코드 포함해서 확인된 것이 없다. 현재 접근에서는 아예 불가능하다는 주장도 있다. 하지만, 채점기가 adaptive하지 않기 때문에, 적절한 휴리스틱을 통해서 쿼리 수를 줄일 수는 있다.

본인이 추가한 최적화는 다음과 같다. 위 이분 탐색을 잘 살펴보면, 결정 문제가 성공했을 때는 "정확히" 중간점 까지만 후보를 줄이지만, 실패했을 때는 기계에 들어간 원소가 중간점에 미치지 못하기 때문에 "중간점 넘어 더" 후보를 줄임을 관찰할 수 있다. 고로, 결정 문제가 성공하는 것보다는 실패하는 것이 조금 더 기댓값이 높다. 그래서 이분 탐색의 중점을 약간 더 오른쪽으로 움직였더니, 만점이 나왔다.

랜덤성 없이, 99.89 풀이의 m = (s + e + 1) / 2를 m = (s + e + 1 + (e - s > 5)) / 2로 10글자만 추가하면 된다.

문제 6. 수천개의 섬

어떠한 카누가 현재 $U[i]$ 에 정박해 있고, $U[i], V[i]$ 를 오간다면, 이 요트를 $U[i] \rightarrow V[i]$ 로 향하는 방향 간선으로 생각할 수 있다. 어떠한 간선을 사용했다면, 이 간선의 방향이 뒤집히는 것이다. 이하 풀이에서는 이러한 방향 그래프 모델링을 사용할 것이고 용어도 이에 맞춘다.

서브태스크 1 (5점)

케이스 분석을 통해서 풀 수 있다.

• $0$ 번 정점에서 $1$ 번 정점으로 가는 간선이 $0$ 개일 경우 출발이 불가능하고, 답이 없다.
• $1$ 번 정점에서 $0$ 번 정점으로 가는 간선이 $0$ 개일 경우 출발 후 $1$ 번 정점에서 돌아올 수 없고, 답이 없다.
• $0$ 번 정점에서 $1$ 번 정점으로 가는 간선이 $1$ 개일 경우, $0, 1, 0$ 번 정점을 들린 이후, 초기 $0$ 번 정점에서 $1$ 번 정점으로 가는 간선을 돌려놓는 것이 불가능하고, 답이 없다.
• 그 외 경우, 항상 답이 존재한다. $0$ 번 정점에서 $1$ 번 정점으로 가는 간선이 ${a, b}$, $1$ 번 정점에서 $0$ 번 정점으로 가는 간선이 $c$ 라고 하자. $[a, c, b, a, c, b]$ 가 가능한 해가 된다.서브태스크 2 (10점)$N \geq 3$ 인 경우, 항상 답이 존재한다. $0 \rightarrow 1 \rightarrow 2 \rightarrow 0$ 으로 도는 사이클 $C_1$과, $0 \rightarrow 2 \rightarrow 1 \rightarrow 0$ 으로 도는 사이클 $C_2$ 가 있을 때, $[C_1, C_2, C_1, C_2]$ 순으로 이어 붙이면 답이 된다.

서브태스크 3 (31점)

간선이 양방향으로 이어져 있으니, $(i, i + 1)$ 번 간선을 그룹으로 묶어서 양방향 간선으로 간주한다.

$0$ 번 정점의 차수가 $2$ 이상이라면, 연결된 정점을 $u, v$ 라고 했을 때, $0 \rightarrow u \rightarrow 0 \rightarrow v \rightarrow 0$ 을 두 번 반복해 주면 해를 찾아줄 수 있다. 비슷하게, $0$ 번 정점에서 도달할 수 있는 차수 $3$ 이상의 정점이 존재한다면, 해당 정점으로 움직인 후, 해당 정점으로 오는 데 사용하지 않은 간선 두개를 사용해서 비슷하게 해 주면 된다.

그렇지 않다면, $0$ 번 정점을 포함하는 연결 컴포넌트는 path의 형태를 띌 것이며 $0$ 번 정점은 그 path의 한 끝점이 된다. 이 경우에는 답이 존재하지 않는다.

서브태스크 4 (55점)

만약 $0$ 번 정점에서 도달할 수 있는 사이클이 없다면, $0$ 번 정점에서 도달할 수 있는 정점들을 위상 정렬할 수 있고, 들어왔던 간선으로 돌아오지 않는 한 모든 이동이 위상정렬상 위치를 증가시킨다. 고로 해가 없다.

그렇지 않다면, $0$ 번 정점에서 사이클로 가는 경로를 $P$ 라고 하자. 같은 방향으로 도는 간선이 쌍으로 있으니, 두 개의 간선이 겹치지 않는 사이클 $C_1, C_2$ 를 얻을 수 있다. $[P, C_1, C_2, C_1, C_2, rev(P)]$ 순으로 이어 붙이면 답이 된다. ($rev(P)$ 는 $P$ 를 뒤집은 경로를 뜻한다.)

만점 풀이

서브태스크를 따라가다 보면, 만점 풀이가 "$0$ 번 정점에서 도달 가능한 어떤 간선이 겹치지 않는 두 개의 사이클" 혹은 유사한 구조를 찾는 방향이라고 생각하기 쉽다. 하지만 이러한 방향으로는 풀이가 나오지 않는다. 서브태스크가 약간 함정인 면이 있다고 생각했다. 이와 별개로 만점 풀이의 관찰 자체가 예상하기 힘들어서, 어렵고 흥미로운 문제라고 생각한다.

만약에 어떠한 정점의 Outdegree가 $0$ 이라고 하자. 이 경우, 어떠한 이동을 통해서 이 정점에 도달하게 되었다면, 다시 나올 수 없게 된다. 고로 이러한 정점은 답의 일부가 되지 않고, 그래프에서 지워줄 수 있다. 정점을 지우는 과정에서, 다른 정점들의 Outdegree가 연쇄적으로 $0$이 나올 수 있는데, 이러한 정점들 역시 계속 지워주자. 이 과정은, 간선들을 Set과 같은 자료구조로 관리하고, 큐를 사용하여 지울 정점의 리스트를 관리하는 식으로 구현할 수 있다. 물론, 이 과정에서 $0$ 번 정점을 지우게 된다면, 해가 존재하지 않는다.

위와 같은 과정을 거치면, 모든 정점의 Outdegree가 $1$ 이상이 된다. $0$ 번 정점 역시, Outdegree가 $1$ 이상일 것이다. 만약 $0$ 번 정점의 Outdegree가 $2$ 이상이면, 여기서 바로 답이 항상 존재함 을 보일 수 있다.

$0$ 번 정점을 제외한 모든 정점에 대해서 나가는 간선을 하나 빼고 전부 삭제하고, $0$ 번 정점에 대해서 나가는 간선을 두 개 빼고 전부 삭제하자. 잠시, $0$ 번 정점에서 나가는 간선을 둘 중 하나만 남긴다면, 이 그래프는 모든 정점의 Outdegree가 정확히 $1$인 functional graph의 모습을 함을 알 수 있다. 고로, $0$ 번 정점에서 사이클 방향으로 전진한 후, 사이클을 타고, 다시 왔던 길로 돌아와 $0$ 번 정점에 도달하는, 콩나물 모양의 (단순하지 않은) 경로를 생각할 수 있다. 이를 $P_1$ 이라고 하자.

$P_1$ 을 탄 후, 사이클의 간선 방향은 반전되지만 다른 간선들은 방향이 유지 된다. 사이클의 간선 방향이 반전된다고 Outdegree가 변하지 않는다. $0$ 번 정점에서 나가는 간선을 아까 하나만 남겼는데, 다른 쪽을 남기게 될 경우 여전히 functional graph의 모습을 한다. 똑같은 방법으로, $0$ 번 정점에서 사이클 방향으로 전진한 후, 사이클을 타고, 다시 왔던 길로 돌아와 $0$ 번 정점에 도달하는, 콩나물 모양의 (단순하지 않은) 경로를 생각할 수 있다. 이를 $P_2$ 이라고 하자. 최종적으로, $[P_1, P_2, P_1, P_2]$ 라는 해를 찾을 수 있다.

이제 $0$ 번 정점의 Outdegree가 $1$ 이라고 하고, 이 나가는 간선을 $e = (0 \rightarrow v)$ 라고 하자. 이 경우, 첫 이동은 $e$ 를 쓸 수 밖에 없다. 또한, 이후 다시 $0$ 번 정점으로 돌아오게 된다면, 그 때 사용한 간선은 $e$ 여야 한다 (그렇지 않다면 경로가 거기서 끝나고, 뒤집은 간선들을 원상복구할 수 없다). $e$ 로 출발한 후, $0$ 번 정점을 중간에 들리지 않고 뒤집힌 $e$ 로 돌아왔다. 다시 나갈 때는 $e$ 로 나갈 수 밖에 없으며 이는 불가능하다.

고로, $0$ 번 정점을 포함하는 해는, $e$ 로 시작하고, $e$ 로 끝나며, 중간에 $0$ 번 정점을 다시 들릴 수 없다. 이는, $0$ 번 정점을 지운 후 귀납적으로 $v$ 를 시작점으로 하는 문제를 해결하면 됨을 뜻한다. 이 과정 속에서 Outdegree가 $0$ 인 정점이 추가적으로 생길 수 있기 때문에, 이 역시 적절히 지워줘야 함에 유의하자.

시간 복잡도는 $O(n + m)$ 이나, std::set 등을 사용하여 $\log$ 를 붙이는 것이 구현에 있어서 더 편할 것 같다.

여담으로, Outdegree가 $2$ 이상인 케이스에서 Functional graph를 일일이 분석할 필요는 없다. 그냥 $0$ 번 정점에서 시작해서, (간선이 뒤집힘과 왔던 간선으로 나갈 수 없음을 감안하며) 갈 수 있는 다음 정점을 아무거나 골라 가는 것을 반복하면, $[P_1, P_2]$ 가 나오기 때문이다.

문제 풀이 한 줄 요약

• circuits: DP 풀이를 고안한 후, 사실은 DP 풀이에서 계산하는 것이 점화식이 아닌 closed form 수식 형태로 떨어짐을 계산. 이후 해당 closed form 수식 계산 및 잡다한 처리를 자료구조로 개선
• insects: 이분 탐색 풀이를 고안한 후, 미정된 후보를 반에 가깝게 줄이는 최적화를 사용하면 99.89점을 획득. 그레이더의 non-adaptive함을 활용할 경우 추가 점수를 얻을 수 있고, 만점 풀이에서는 이것이 필요.
• islands: outdegree가 0인 정점은 지워도 되고, 모든 정점의 outdegree가 1 이상이면 답이 항상 존재한다는 아이디어를 고안. Functional graph의 구조를 사용하여 이 아이디어를 증명.