koosaga's profile image

koosaga

September 1, 2022 00:00

IOI 2022

IOI 2022 대회가 종료되었다. 올해 대회의 개최지는 인도네시아에서 진행하며, 온라인 대회 역시 병행한다. 한국 팀은 온라인 참가를 결정하였기 때문에, 현재 서울에서 모여서 감독 하에 대회를 진행하고 있다.

이 글에서는 해당 대회에 출제된 문제들을 하나 하나 풀어보고, 그 풀이를 소개한다. IOI에는 다양한 문제가 나오기 때문에 모든 풀이를 하나의 주제로 요약할 수는 없다. 고로 각 풀이의 핵심 키워드를 아래에 정리하였다.

구현한 풀이는 모두 https://github.com/koosaga/olympiad/tree/master/IOI 에서 찾을 수 있다.

문제 풀이 한 줄 요약

• fish: 문제 구조에 대한 관찰을 통해서 최적해의 구조를 제약시키고, 제약된 구조 안에서 DP를 사용하여 해결한 후 자료구조를 사용하여 계산을 고속화
• prison: $2 \log N$ 개의 쿼리를 사용하는 전략을 구상 후 몇 가지 국소적 최적화를 고안. 이러한 국소적 최적화로 얻을 수 있는 이론상 쿼리 최소치를 찾은 후 이에 따라 구현.
• towers: 최적해가 배열의 극소/극대점 만 사용한다는 점을 관찰한 후, 답에 포함되지 않는 극소/극대점을 반복적으로 지우는 식의 알고리즘 고안. 이후 해당 알고리즘이 사실 모든 D, 모든 구간 쿼리에 대한 답을 구함을 관찰하고 그에 맞게 자료 구조 등을 사용하여 수정
• circuits: DP 풀이를 고안한 후, 사실은 DP 풀이에서 계산하는 것이 점화식이 아닌 closed form 수식 형태로 떨어짐을 계산. 이후 해당 closed form 수식 계산 및 잡다한 처리를 자료구조로 개선
• insects: 이분 탐색 풀이를 고안한 후, 미정된 후보를 반에 가깝게 줄이는 최적화를 사용하면 99.89점을 획득. 그레이더의 non-adaptive함을 활용할 경우 추가 점수를 얻을 수 있고, 만점 풀이에서는 이것이 필요.
• islands: outdegree가 0인 정점은 지워도 되고, 모든 정점의 outdegree가 1 이상이면 답이 항상 존재한다는 아이디어를 고안. Functional graph의 구조를 사용하여 이 아이디어를 증명.

문제 1. 메기 농장

서브태스크 1 (3점)

$X$ 좌표가 홀수인 모든 지점에 길이 $N$ 의 낚시터를 설치하면, 모든 메기를 잡을 수 있다. 답은 $W[i]$ 의 합이다.

서브태스크 2 (9점)

$X = {0, 2, \ldots}$ 인 지점에 길이 $N$ 의 낚시터를 설치하면 $X[i] = 1$ 인 메기를 모두 잡을 수 있다. $X = 1$ 인 지점에 길이 $N$ 의 낚시터를 설치하면 $X[i] = 0$ 인 메기를 모두 잡을 수 있다.

$N = 2$ 일 때는 $X[i]$ 가 다른 메기를 동시에 잡을 수 없기 때문에, 둘 중 하나의 선택을 하면 된다.

$N > 2$ 일 때는 $X = 2$인 지점에 낚시터를 설치한다고 다른 메기를 잡지 못하게 되는 일이 없다. 또한, $X = 2$ 인 지점에 낚시터를 설치했다면 $X = 0$ 인 지점에 낚시터를 설치할 이유가 없다. 고로 $X = 1$ 인 지점에 설치하는 낚시터의 길이만 적절히 조절해 주면 된다. 각 길이에 대해서 잡을 수 있는 메기의 수가 부분합 형태로 계산 가능하여, 모든 길이를 시도해 보면 된다.

서브태스크 4 (32점)

서브태스크 $3, 4$ 에서는 $Y$ 좌표의 제한이 작다는 점을 활용한다. (서브태스크 3은 조금 더 간단한 DP 풀이가 있으나 굳이 설명하지 않는다.)

$h[i]$ 를 $i$번 열에 설치한 낚시터의 길이라고 하자 ($h[-1], h[N]$ 등은 모두 $0$ 으로 간주한다). 낚시터의 길이가 고정되어 있을 때, 위치 $(i, j)$ 에 있는 메기가 잡힌다는 것은, $h[i] \leq j < max(h[i - 1], h[i + 1])$ 를 만족한다는 것과 동치이다. 이를 토대로 DP를 할 수 있다.

$DP[i][k][j]$ 를, $h[i - 1] = k, h[i] = j$ 일 때, $0 \ldots i - 1$ 번 열에서 잡은 메기의 무게 합 최대라고 정의하자. 모든 가능한 $h[i - 2] = l$에 대해서 상태 전이를 하는데, 이 때의 가중치는 $DP[i - 1][l][k]$ 에, $i - 1$ 번 열에서 잡게 될 메기의 무게 합을 더한 값이 된다.

$i - 1$ 번 열에서 잡게 될 메기는 $[k, max(l, j))$ 행 구간에 존재한다. 이 영역의 무게 합은 초기 전처리 후 $O(1)$ 에 계산할 수 있다. 이 계산 결과를 통해서 상태를 전이한다.

시간 복잡도는 $O(N Y^3)$ 이다.

서브태스크 5 (53점)

서브태스크 4의 풀이를 약간 더 개선하면 된다. $DP[i][k][j]$ 의 상태 전이를 수식으로 풀어서 명확하게 해 보자. $S[i][j]$ 를, $i$ 번 열의 $[0, j - 1]$ 번 행에 존재하는 메기의 무게 합이라고 하면

$DP[i][k][j] = \max_{l} DP[i - 1][l][k] + max(0, S[i - 1][max(l, j)] - S[i - 1][k])$

이라는 식이 도출된다. 이는 풀어서

$DP[i][k][j] = max(\ \max_{l} DP[i - 1][l][k], \ \max_{l} DP[i - 1][l][k] + S[i - 1][max(l, j)] - S[i - 1][k])$

라고 쓸 수 있다.

이 중 $\max_{l} DP[i - 1][l][k]$의 경우, $(i, k)$ 에 고정된 상수이기 때문에, 한 번만 단순 반복문을 돌려주면 쉽게 계산할 수 있다. 고로 두 번째 항을 보자. 두 번째 항의 경우 두 가지 케이스가 있다.

• Case 1. $l \le j$. 이 경우 $\max_{l \le j} DP[i - 1][l][k] + S[i - 1][l] - S[i - 1][k]$ 를 계산하면 된다. $(i, k)$ 가 고정된 경우 위 식은 Prefix max의 형태를 띈다. $j$ 를 증가하면서, $l = j$ 일 때의 경우를 갱신해 주는 것을 반복하는 식으로 값을 관리할 수 있다.
• Case 2. $l > j$. 이 경우 $\max_{l > j} DP[i - 1][l][k] + S[i - 1][j] - S[i - 1][k]$ 를 계산하면 된다. $(i, k)$ 가 고정된 경우 위 식은 Suffix max의 형태를 띈다. $j$ 를 감소하면서, $l = j+1$ 일 때의 경우를 갱신해 주는 것을 반복하는 식으로 값을 관리할 수 있다.

이를 통해 각 항을 $O(1)$ 시간에 채울 수 있다. 전체 상태가 $O(N^3)$ 개이니, 시간 복잡도는 $O(N^3)$ 이다.

만점 풀이

서브태스크 5에서의 DP 풀이가 만점을 받기에는 너무 무겁기 때문에, 몇 가지 관찰을 통해서 구조를 제약시키고, 더 단순한 DP를 얻는 것이 목표이다.

각 열을 낚시터가 있는 경우와 없는 경우로 분리할 수 있는데, 이 중 낚시터가 있는 연속된 열 구간들을 컴포넌트 라고 정의하자. 즉, 컴포넌트 구간 $[L, R]$ 안에 속하는 열들은 모두 길이 1 이상의 낚시터가 있고, 구간의 양 끝 밖 ($L - 1, R + 1$) 에 있는 열들은 낚시터가 없다.

이렇게 각 열들을 컴포넌트로 묶게 될 경우 좋은 성질들을 관찰할 수 있다. 첫 번째로, 컴포넌트를 이루는 낚시터의 길이는 계곡 을 이루는 경우가 없다. 만약 컴포넌트 안의 낚시터의 길이가 $a > b < c$ 와 같이, 중간에 있는 원소가 양 끝 인접한 원소보다 작은 경우가 있다고 하자. 이 경우, $b = 0$ 으로 두어서, 중간에 있는 낚시터를 아예 없앨 경우, 더 많은 메기를 잡을 수 있다. 고로 최적해에서는 이러한 경우가 없다고 가정할 수 있고, 이것은 낚시터의 길이를 순서대로 봤을 때, 낚시터의 길이가 증가하다가 감소하는 수열 의 형태를 띈다는 것을 뜻한다.

어떠한 컴포넌트 $[L, R]$ 의 최댓값이 $X$ 에 형성되어 있다면, $[L - 1, X - 1]$ 구간에서 우리는 $Y[i]$ 가 우상향하는 방향으로 메기를 잡을 수 있고, $[X + 1, R + 1]$ 구간에서 우리는 $Y[i]$ 가 우하향하는 방향으로 메기를 잡을 수 있다. 저 문제는 조금 더 쉬워 보이니, 저러한 쉬운 문제를 컴포넌트마다 독립적으로 해결하고 합쳐줄 수 있으면 좋을 것이다. 하지만 한 가지 걸리는 것은, 두 컴포넌트가 하나의 빈 열만 두고 인접했을 때, 해당 열에 있는 메기를 두 컴포넌트에서 중복해서 세어줄 수 있다는 것이다. 이를 해결하기 위해 두 번째 관찰을 하자.

두 번째로, 두 컴포넌트 $[z, x - 1], [x + 1, y]$ 가 하나의 빈 열 $x$ 만을 두고 인접했을 경우, $x$에 인접한 부분인 $H[x - 1], H[x + 1]$ 이 $N$ 이라고 가정할 수 있다는 것이다. 이유는 다음과 같다.

• 만약에 $H[x - 2] \geq H[x - 1]$ 혹은 $H[x + 1] \le H[x + 2]$ 라고 하자. 일반성을 잃지 않고 $H[x - 1] \le H[x + 1]$ 이라 하면, $H[x - 1] = 0$ 으로 바꿨을 때 잡을 수 있는 메기의 수가 줄어들지 않는다. 고로 두 컴포넌트가 하나의 빈 열을 두고 인접하지 않다 가정할 수 있다.
• 고로 $H[x - 2] < H[x - 1], H[x + 1] > H[x + 2]$ 를 만족한다. 이 경우에는 $H[x - 1] = H[x + 1] = N$ 으로 바꿨을 때 잡을 수 있는 메기의 수가 줄어들지 않는다.

이러한 형태로 인접한 두 컴포넌트는 최댓값이 컴포넌트의 한 쪽 끝에 형성되어 있으니, 컴포넌트 자체가 최댓값 하나로만 이루어져 있거나, 아니면 최댓값을 기준으로 감소 / 증가 하는 형태를 띌 것이다. 두 컴포넌트 사이에 하나의 빈 열만 존재한다면 두 컴포넌트를 인접 하다고 하고, 인접한 컴포넌트들의 집합을 슈퍼컴포넌트 라고 하자. 슈퍼컴포넌트는 다음과 같은 구조를 이룬다:

• 가장 왼쪽에 있는 컴포넌트는 높이가 증가하며 오른쪽 끝의 높이가 $N$ 이다.
• 가장 오른쪽에 있는 컴포넌트는 높이가 감소하며 왼쪽 끝의 높이가 $N$ 이다. (왼쪽에 있는 컴포넌트랑 붙어 있을 수도 있다.)
• 그 사이에 있는 컴포넌트는 높이가 $N$ 이며 길이가 전부 $1$ 이다. (없을 수 있다.)

가장 왼쪽에 있는 컴포넌트가 열 $[L, M]$ 을 차지하고, 그 사이에 $M + 2, M + 4, \ldots, M + 2k$ 위치에 길이 1의 컴포넌트가 있고, 가장 오른쪽에 있는 컴포넌트가 열 $[M + 2k + 2, R]$ 을 차지한다고 하자. ($k \geq 0$) 이 때 우리가 잡게 되는 메기는

• 열 $[L - 1, M - 1]$ 구간에 있는, $(x, y)$ 좌표가 모두 단조증가하는 메기들의 체인
• 열 $M + 1, M + 3, \ldots, M + 2k + 1$ 에 있는 모든 메기들
• 열 $[M + 2k + 3, R + 1]$ 구간에 있는, $x$ 좌표가 단조증가하고 $y$ 좌표가 단조감소하는 메기들의 체인

(왼쪽 컴포넌트와 오른쪽 컴포넌트가 붙은 경우는 생략했다.)

이제 최적해의 형태를 충분히 제약시켰다. 위 최적해를 DP로 표현해 보자.

• $DP[i] = i$ 번 이하의 열을 슈퍼컴포넌트로 묶었을 때 메기 무게의 최대 합.
• $Down[p] = p$ 번 점을 감소 체인의 마지막 점으로 두었을 때 메기 무게의 최대 합.
• $Top[i] = i$ 번 열에 낚시터가 없을 때 메기 무게의 최대 합.
• $Up[p] = p$ 번 점을 감소 체인의 마지막 점으로 두었을 때 메기 무게의 최대 합.

다음과 같이 전이할 수 있다.

• $DP[i] = max(DP[i - 1], Top[i - 1], \max_{X[p] = i}Down[p])$
• $Down[p] = \max(Top[X[p] - 2], \\max_{X[q] \le X[p], Y[q] > Y[p]} Down[q]) + W[p]$
• $Top[i] = \max(Top[i - 2] + \sum_{X[p] = i} W[p], \\max_{X[p] = i} Up[p])$
• $Up[p] = \max(DP[X[p] - 1], \\max_{X[q] \le X[p], Y[q] < Y[p]} Up[q]) + W[p]$

이것을 단순하게 계산할 경우 $O((N + M)^2)$ 시간이 걸린다. 상태가 $N + M$ 개이고 전이 역시 다른 상태를 다 탐색하기 때문이다. 이 중 대다수 전이들은 보조 배열을 전처리하는 선에서 간단하게 최적화가 된다. $Down$ 과 $Up$ 에서 사용하는 전이는 단순하게 해결하기 어려운 편에 속하는데, $X[i]$ 를 증가시켜나가면서 처리할 경우, $Y[i]$ 좌표를 Key로 가지는 Max Segment Tree를 두면 이 역시 처리가 가능하다.

종합하면, 모든 상태 전이가 $O(\log N)$ 시간에 가능하여, 전체 문제가 $O((N + M) \log N)$ 에 해결된다.

문제 2. 죄수들의 도전

5점 풀이

5점 풀이는 문제를 이해했다면 어렵지 않다. 다음과 같이 프로토콜을 구성한다.

• 수 $0$ 이 쓰여졌다면, A번 가방을 열어서 동전 개수를 확인하고, 동전 개수를 적는다.
• $0$ 이 아닌 수가 쓰여있다면, 칠판에 적힌 수가 A번 가방에 있는 동전의 개수이다. B번 가방에 있는 동전 개수를 확인해 보면, 동전이 적게 든 가방을 고를 수 있다.

38점 풀이 ($m = 38$)

만약에 적힌 수가 $1, 2$ 중 하나라면, 위 풀이는 $3$ 개의 상태를 사용하여 두 수를 구분할 수 있다. 두 가방에 적힌 동전 개수를 이진 전개한 후, 위 풀이를 $\log N$ 번 반복하는 것으로, 상태 개수를 $O(N)$ 에서 $O(\log N)$ 개로 줄인다. 어떠한 수의 $k$ 번째 비트라는 것은, 해당 수를 $2^k$ 로 나눈 몫의 홀짝성을 뜻한다.

• 수 $0$ 이 쓰여졌다면, $A$ 번 가방을 열어서 $12$ 번째 비트를 확인한다. 만약 이 비트가 $0$ 이라면 칠판에 $1$을, $1$ 이라면 $2$를 쓴다.
• 수 $1, 2$ 가 쓰여졌다면, $B$ 번 가방을 열어서 $12$ 번째 비트를 확인한다. 이 비트가 $A$의 그것과 다르다면 대소를 확인할 수 있다. 그렇지 않다면, 칠판에 $3$ 을 써서 다음 절차로 넘어간다.
• 수 $3, 4, 5$ 에 대해서 $11$번째 비트로 위와 동일한 과정을 반복한다.
• …
• 수 $36, 37, 38$ 에 대해서 $0$번째 비트로 위와 동일한 과정을 반복한다. 칠판에 $39$ 를 써야 할 이유는 없다.

최종적으로 $x \le 38$ 로 문제를 해결할 수 있다.

56점 풀이 ($m = 26$)

위 풀이에서는 $A$ 번 가방과 $B$ 번 가방의 역할에 명확한 비대칭성이 있다. $A$ 는 가방을 연 다음 그 정보를 다음 상태로 넘기고, $B$는 상태를 받은 후 판별만 하고 다시 $A$ 에게 턴을 넘긴다.

사실, $B$ 가 가방을 열 때 꼭 비트 하나만 보는 것은 아니다. $B$ 는 가방의 비트 수를 전부 볼 수 있다. 고로 대소를 확인한 이후, 무의미하게 $A$ 에게 턴을 넘겨줄 필요가 없고, 그 과정에서 더 낮은 비트를 확인하고 다음 상태로 넘기는 걸 같이 해 주면 된다. 이를 써보면 다음과 같다.

• 수 $0$ 이 쓰여졌다면, $A$ 번 가방을 열어서 $12$ 번째 비트를 확인한다. 만약 이 비트가 $0$ 이라면 칠판에 $1$을, $1$ 이라면 $2$를 쓴다.
• 수 $1, 2$ 가 쓰여졌다면, $B$ 번 가방을 열어서 $12$ 번째 비트를 확인한다. 이 비트가 $A$의 그것과 다르다면 대소를 확인할 수 있다. 그렇지 않다면, $B$ 의 $11$ 번째 비트가 $0, 1$ 인지에 따라 칠판에 $3, 4$ 을 써서 다음 절차로 넘어간다.
• 수 $3, 4$ 가 쓰여졌다면, $A$ 번 가방을 열어서 $11$ 번째 비트를 확인한다. 이 비트가 $B$의 그것과 다르다면 대소를 확인할 수 있다. 그렇지 않다면, $A$ 의 $10$ 번째 비트가 $0, 1$ 인지에 따라 칠판에 $5, 6$ 을 써서 다음 절차로 넘어간다.
• …
• 수 $25, 26$ 에 대해서 $B$ 의 $0$번째 비트로 위와 동일한 과정을 반복한다. 칠판에 $27, 28$ 을 써야 할 이유는 없다.

65점 풀이 ($m = 24$)

꼭 이진 전개를 할 필요가 없다. $3$ 진수로 전개할 경우 $3^8 = 6561 \geq 5000$ 이라 모든 수를 판별할 수 있으며, 상태 수도 $3 \times 8$ 로 24개로 줄어든다. 이렇게 구현할 경우 9점을 더 받을 수 있다.

80점 풀이 ($m = 22$)

마지막 스텝에서 약간의 비효율성을 관찰할 수 있다. 위 풀이대로라면, 수 $19, 20, 21$ 이 쓰여졌을 때, 가방을 열어서 $B$의 $0$ 번째 비트를 확인하고 이에 따라서 다음 상태로 넘어갈 것이다. 하지만, $B$ 의 $0$ 번째 비트가 $0$일 경우 $B$ 는 무조건 $A$ 보다 작고, $2$ 일 경우 $B$ 는 무조건 $A$ 보다 크다. 두 수가 항상 다르기 때문이다. 고로, $B$ 의 $0$ 번째 비트가 $1$ 인 경우만 흥미로운 경우이다. 이 점을 관찰하면 두 개의 상태를 절약하여 15점을 더 받을 수 있다.

만점 풀이 ($m = 20$)

만점 풀이에서는, 위 $56$ 점 풀이를 줄이기 위해 사용한 두 가지의 작은 관찰들을 일반화해서, 위 관찰들로 Generate할 수 있는 모든 결정 방법 중 최적을 DP로 계산한다.

첫 번째 관찰은 이진 전개가 아니라 3진 전개를 해도 된다는 관찰이다. 더 나아가서, 전체 문제 자체가 일관된 전개를 할 필요는 없다. 첫 번째 단계에서는 $2$ 로 분할, 두 번째 단계에서는 $3$ 으로 분할, 세 번째 단계에서는 $4$ 로 분할… 하는 등 매번 사용할 수 있는 분할을 달리할 수 있다.

두 번째 관찰은 마지막 단계에서만 사용할 것 같아서 일반화가 힘들어 보이지만, 실제로는 그렇지 않다. 예를 들어서, 맨 처음에 $A$ 안에 들어 있는 동전의 수가 $1, N$ 중 하나라면, 더 이상 판단을 계속할 필요가 없다. $B$ 의 동전의 수가 다르기 때문에 바로 답을 판별할 수 있기 때문이다. 그렇지 않다면, 남은 동전의 수 후보는 $N - 2$ 개이다. 이들 중 구간을 $k$ 개로 나눈 후 $A$ 의 동전 수가 어떤 구간에 속하는지를 보내준다. $B$ 는 그 구간을 받은 후, 만약 내 동전 수가 해당 구간에 속하지 않으면 종료하고, 동전 수가 해당 구간의 양 끝점에 속하면 바로 판별하고, 아니면 분할을 계속 하면 된다.

첫 번째 관찰과 두 번째 관찰을 종합하면, 우리는 다음과 같은 수열 $k_1, k_2, \ldots, k_p$ 를 찾으면 된다:

• $\sum k_i$ 가 가능하면 작음
• $f_i(N) = \lceil (N - 2) / k_i \rceil$ 일 때, $f_p(f_{p - 1}(\ldots (f_1(N)))) = 1$

이러한 수열은 DP, 백트래킹 등 어떠한 방법으로든지 찾을 수 있다. $\sum k_i = 20$ 인 수열이 존재하며, 해당 수열로 위 전략을 구현하면 만점을 받을 수 있다. 가능한 수열 중 하나가 ${3, 3, 3, 3, 3, 3, 2}$ 라는 사실이 구현을 단순화하는 데 도움을 줄 수 있다. 여담으로 $\sum k_i \le 19$ 인 수열은 존재하지 않으니, 지금까지의 풀이 내용만 사용해서 더 좋은 풀이는 얻기 힘들 것이라 짐작이 된다.

문제 3. 송신탑

서브태스크 2 (11점)

어떠한 송신탑 부분집합이 답이 되기 위해서는 부분집합에 속하는 모든 탑 쌍이 서로 통신할 수 있어야 한다. 즉, 일종의 클리크를 이뤄야 하는데, 이렇게 생각하면 풀기 너무 어려우니, 조건을 더 단순화시켜보자.

송신탑 $x < y < z$ 에 대해서, $x, y$ 와 $y, z$ 가 통신할 수 있다면, $x, z$ 역시 통신이 가능함을 관찰할 수 있다.

• $x, y$ 가 통신할 수 있다는 것은, $[x + 1, y - 1]$ 구간에 $H[x] \le H[k] - D$ 인 $k$ 가 존재한다는 것이다.
• $y, z$ 가 존재한다는 것은, $[y + 1, z - 1]$ 구간에 $H[z] \le H[k] - D$ 인 $k$ 가 존재한다는 것이다.
• 고로, $x, z$ 에 대해서, $[x + 1, z - 1]$ 구간에서 저러한 $k$가 존재한다.

고로, 모든 탑 쌍이 서로 통신할 수 있다는 것은, 인접한 탑 쌍이 서로 통신할 수 있다는 것과 동치이다. 이제 DP로 문제를 해결할 수 있다. $DP[i]$ 를, $0, \ldots, i$ 번 점에 대해서, $i$ 번 송신탑을 포함하는 최적해의 최대 크기라고 정의하고, 통신 가능한 모든 $j < i$ 에 대해서 상태를 전이하면 된다. 통신 가능 여부는, $[j + 1, i - 1]$ 구간 최댓값을 관리하면 쉽게 계산할 수 있다. 답은 전체 $DP$ 배열의 최대이고, 시간 복잡도는 쿼리당 $O(N^2)$ 이다.

서브태스크 3 (23점)

두 송신탑 $i, j$ 가 통신하기 위해서는, 둘 사이에 송신탑 $k$ 가 존재하여, $H[i] + D \le H[k], H[j] + D \le H[k]$ 가 모두 만족된다는 뜻이다. $i, (k), j$ 와 같이, 중간에 이러한 송신탑을 끼워넣으면

• 인접한 원소간의 높이 차가 $D$ 이상이고
• 높이가 증가했다 감소한다

는 것을 관찰할 수 있다.

$i, j$ 가 송신탑일 때, 이렇게 $i, j$ 간의 송신을 도와주는 송신탑을 매개 송신탑 이라고 정의하자. 그리고, 송신탑의 최대 부분수열 $i_1, i_2, \ldots, i_k$ 를 구하는 대신, 매개 송신탑을 포함하는 최대 부분수열 $i_1, (j_1), i_2, (j_2), \ldots, i_{k-1}, (j_{k-1}), i_k$ 를 구하는 것으로 문제를 변형하자. 이렇게 할 경우, 최댓값에 대한 이야기를 할 필요 없이, 인접한 원소 간의 높이 차만 보면 되어서 편리하기 때문이다. DP를 다시 써 보자.

• $Up[i]$ 를, $i$ 번 송신탑을 매개 송신탑 으로 쓰는 부분 집합의 최대 크기
• $Down[i]$ 를, $i$ 번 송신탑을 쓰는 부분 집합의 최대 크기

라고 정의하면, $Up[i] = \max_{j < i, H[j] \le H[i] - D} Down[j], Down[i] = \max_{j < i, H[j] \ge H[i] + D} Up[j] + 1$ 와 같은 점화식이 성립한다. $H$ 를 좌표압축한 후, $Down, Up$ 배열을 좌표압축된 $H[i]$ 를 Key로 하는 Max Segment Tree로 관리할 경우 문제가 해결된다.

시간 복잡도는 쿼리당 $O(N \log N)$ 이다.

서브태스크 5 (40점)

서브태스크 3을 기준으로 이런 저런 관찰을 하다보면 서브태스크 5의 풀이가 얻어진다. 두 송신탑 $i, i + 1$ 에 대해서, $H[i] < H[i + 1]$ 이면 빨간 간선, $H[i] > H[i + 1]$ 이면 파란 간선으로 두 송신탑을 이어주자. 그렇다면 송신탑들은 길이 $N - 1$ 의 직선으로 연결될 것이며, 직선은 빨간 간선의 연속구간과 파란 간선의 연속구간으로 분할할 수 있을 것이다. 이제 여기서, (매개 송신탑을 포함하여) 송신탑의 부분집합을 고를 때, 다음과 같은 성질들이 성립한다.

• 같은 색으로 이루어진 간선 연속구간 안에서, 세 개 이상의 송신탑이 부분집합에 들어갈 수 없다. (높이가 증/감을 번갈아 해야 하기 때문에 정의상 자명)
• 같은 색으로 이루어진 간선 연속구간 안에서 골라야 하는 송신탑은, 연속구간의 양 끝점 뿐이다. (그렇지 않을 경우, 매개 송신탑은 값이 큰 쪽, 송신탑은 값이 작은 쪽으로 밀어넣으면 된다.)

이 관찰을 통해서, 중간에 있는 의미없는 원소를 제거해 주면서 송신탑의 높이가 증가/감소를 번갈아가게끔 할 수 있다. 하지만, 그렇다고 인접한 원소의 차이가 $D$ 이상임이 바로 보장되는 것이 아니라, 이것만으로는 바로 문제가 해결되지 않는다. 추가로 한 가지 관찰이 더 필요하다.

• 인접한 원소 간의 차가 가장 작은 송신탑 $(i, i + 1)$ 에 대해, 만약 $1 \le i \le N - 3$ 이고, 두 송신탑의 원소 차이가 $D$ 미만이라면, 두 송신탑을 모두 사용하지 않는 최적해가 존재한다.
  • 정의 상 두 송신탑을 모두 사용하는 해는 당연히 없다. 일반성을 잃지 않고 $H[i] < H[i + 1]$ 이며, $i$ 가 일반 송신탑이라고 하자. $i$ 가 일반 송신탑이기 때문에 $i + 2$ 는 현재 해에 포함되어 있지 않다. 또한 가정에 의해 $H[i] \geq H[i + 2]$ 이다. 고로 $i$ 를 $i + 2$ 로 대체시키면 된다.

고로, 이러한 경우에는 두 송신탑을 제거해 줄 수 있다. 이제 고정된 $D$ 에 대해서, 위와 같은 증/감이 번갈아 등장하는 송신탑을 std::set과 같은 자료구조에, 인접한 송신탑의 높이 차와 위치를 Heap과 같은 자료구조에 관리하자. 모든 송신탑의 원소 차이가 $D$ 이상이 될 때까지, 위와 같이 송신탑들을 적절히 지워준 후, 최후에 std::set의 크기를 통해서 송신탑 부분 집합의 크기를 계산하면 된다. 양 끝점 처리는 위 관찰로 바로 되지 않으니 적절히 처리해 줘야 한다.

이제 서로 다른 $D$ 값에 대해서도 문제를 해결해야 하는데, 사실 위 풀이는 모든 $D$ 에 대해서 최적 송신탑 집합을 관리함을 관찰할 수 있다. 수열의 길이가 $1$ 이 될 때까지 인접한 송신탑을 지워준 후, 매 연산 이후 집합의 크기를 기록해 두자. 쿼리로 $D$ 가 주어지면, $D$ 미만의 원소 차이를 모두 지운 직후 집합의 크기를 반환하면 된다.

시간 복잡도는 $O((N + Q) \log N)$ 이다.

만점 풀이

구간이 $[0, N - 1]$ 이 아니더라도 풀이 자체가 큰 차이가 나지는 않는다. 구간에서 현재 제거하지 않은 송신탑의 개수에, 구간의 양 끝점 처리만 적절히 더해주면 되기 때문이다.

현재 제거하지 않은 송신탑의 개수는, $D$ 혹은 그 이후에 지워진 송신탑의 개수와 동일하다. 40점 풀이에서 (매개 송신탑 아닌) 송신탑을 제거할 때, 송신탑이 지워진 시점과 그 위치를 기록해 둔다. 각각의 쿼리가 들어올 때, $D$ 이후에 지워진 송신탑 중 구간 $[L, R]$ 에 있는 송신탑의 개수를 센다. 이는 Persistent Segment Tree로 해결할 수 있다.

양 끝점 처리를 하기 위해서는, 현재 제거하지 않은 송신탑 중 가장 왼쪽 / 오른쪽에 있는 송신탑을 알아야 한다. 위에서 사용한 Persistent Segment Tree를 동일하게 사용하면 된다. 이후 이 왼쪽과 오른쪽에 추가로 송신탑이 더 올 수 있는지는, 구간 최대 / 최솟값을 빠르게 구할 수 있으면 해결 가능하다.

시간 복잡도는 $O((N + Q) \log N)$ 이다.

문제 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]$ 가 나오기 때문이다.