APIO 2020
올해 학생들 성적은 1금5은으로 예년과 비슷한 편으로 보인다. 반딧불이 300점 만점에 300점을 받아서, 2015년 이후 첫 APIO 만점과 함께 금메달을 얻었다. 반딧불 학생은 올해 IOI 국가대표이기도 한데, 아직 고등학교 1학년이니 앞으로도 좋은 결과가 기대된다. 그 뒤를 이어 이온조, 최서현, 장태환, 김지훈, 최은수 학생이 은메달을 얻었다. 모두 축하합니다!
1. 벽 칠하기
Subtask 1 (12점)
특정 벽을 칠할 수 있는 일꾼이 누구인지 고정되어 있다. 고로 색에 대해서 신경쓸 필요가 없고, 각 일꾼들이 문제의 조건에 맞게 구간을 칠하게 하면 된다. 같은 일꾼으로 된 연속된 구간들로, 벽을 분리하자. 만약 길이가 $M$ 미만인 구간이 있다면 벽을 칠할 수 없다. 그렇지 않다면, 구간의 길이가 $L$ 일 때, 일꾼은 $\lceil \frac{L}{M} \rceil$ 번 구간을 칠해야 한다. 이 값을 합해주면 된다. 특정 색을 칠할 수 있는 일꾼이 누구인지는 배열 등에 저장하면 쉽게 구할 수 있다. 시간 복잡도는 $O(N + M + \sum f(k))$ 이다.
Subtask 3 (40점)
입력이 작기 때문에, 모든 가능한 지령 $(x, y)$ 에 대해서 각 지령을 처리할 수 있는지를 판별할 수 있다. 단순하게는 문제에서 지령을 처리하는 조건이 전부 나와있기 때문에, 어떠한 일꾼이 해당 색을 좋아하는지 여부만 이분 탐색으로 찾아주면 된다. 이렇게 해 줘도 문제에서 주어진 제한에서는 충분히 빠를 것으로 보인다.
이걸 더 깔끔하게 보는 방법도 있는데, $N \times M$ 크기의 배열 $canPaint[i][j]$ 를 정의하자. $canPaint[i][j]$ 는, $i$ 번 일꾼이 $j$ 번 벽을 칠할 수 있으면 1, 아니면 0을 칠해주는 식으로 채워진다. 이는, $C[j]$ 번 색을 $i$ 번 일꾼이 좋아하면 1, 아니면 0이라는 것과 동일하니, 각 색에 대해서 해당 색을 칠할 수 있는 일꾼의 리스트를 구해주면 해당 배열을 채워줄 수 있다.
특정 지령 $(*, y)$ 가 처리 가능하다는 것은, $[y, y + M - 1]$ 구간에 있는 벽을 칠해줄 수 있다는 뜻이다. 즉, 전체 문제는, 길이 $M$ 의 구간이 주어질 때, 최소한의 구간을 사용하여 배열 전체를 덮는 문제가 된다. 이는 끝점 순으로 정렬한 후 Greedy를 사용하면 된다. (본인은 priority queue로 최적화된 DP를 사용하였으나, 왜 그렇게 했는지 모르겠다.)
전처리에 $O(\sum f(k))$. 가능한 지령이 $O(NM)$ 개, 각 지령을 판별하는 데 $O(M)$, 모든 것을 확인한 후 Greedy를 돌릴 때 $O(N)$ 시간이 드니, 시간 복잡도는 $O(NM^2)$ 이다.
Subtask 4 (63점)
여전히 제한이 아주 크지 않기 때문에, 특정 지령이 가능한지를 빠르게 판별해주면 된다. 지령 $(x, y)$ 가 가능하다는 것은, $canPaint[(x + l) \% m][y + l]$ 이 모든 $0\le l \le m-1$ 에 대해 참이라는 뜻이다.
이렇게만 해도 부분합을 적당히 더럽게 구해주면 해결할 수 있을 것 같으나, 깔끔한 구현을 위해서, $canPaint2[i][j] = canPaint[(i + j)\%m][j]$ 로 정의하자. 이제 지령 $(x, y)$ 가 가능하다는 것은, $canPaint2[(x - y) \% m][y + l]$ 이 모든 $0 \le l \le m - 1$ 에 대해 참이라는 뜻이다 (당연하지만 음수에 mod 취해주는 것은 조심하자).
이제 문제는 $canPaint2[(x - y)\%m]$ 배열의 $[y, y + m - 1]$ 구간 합이 $m$ 인지를 묻는 문제로 변형되었다. 부분 합 배열을 사용해서 해결해 주면 된다. 시간 복잡도는 $O(NM)$ 이다.
만점 풀이
$\sum f(k)^2 \le 400000$ 이기 때문에 각 $f(k) \le 650$ 이다. 이는 특정 색을 좋아하는 일꾼이 최대 650명이라는 것이다. 즉, 각 벽을 칠할 수 있는 일꾼이 최대 650명이니, 다른 말로 $canPaint2[i][j]$ 배열에서 1인 값은 많아야 $650N$ 개이다. 이 점을 활용해서 알고리즘을 최적화해보자. 일단 우리는 모든 $x, y$ 에 대해서 지령 $(x, y)$ 가 처리 가능한지를 다 알아야 하는 것이 아니라, 모든 $y$에 대해서 지령 $(x, y)$가 처리 가능한 $x$가 존재하는지만 알면 된다. 고로, 0번 벽부터 $n-1$번 벽까지 순서대로 스캔한 후, $ y+m-1$ 번 벽을 처리할 때 $(*, y)$ 형태의 지령이 있는지 정도만 확인할 수 있다면, 위에서 사용한 그리디를 그대로 사용할 수 있다.
일단, $canPaint2[i][j]$ 배열의 부분 합을 관리할 수는 없다. 사실 합 자체는 관리할 수 있지만, 구간 쿼리를 할 수가 없다. 그러니 구조를 바꾸자. 지령 $(x, y)$ 가 가능한지 여부는 특정 위치에서부터 시작하는 길이 $m$ 의 1이 있는지에 따라서 결정되니, $DP[i][j] = $ ($canPaint2[i][j]$ 에서 왼쪽으로 가장 멀리 갔을 때 얼마나 갈 수 있는지) 로 저장하자.
$DP[i][j]$ 는 다음과 같이 결정된다.
- $canPaint2[i][j]$ 가 참이면 $DP[i][j-1] + 1$
- 아니면 0
$DP[i][j]$ 의 전이가 정말 간단하기 때문에, $DP[i][j-1]$ 배열을 $DP[i][j]$ 배열로 바꿔가면서 필요한 값을 관리할 수 있다. 우리는 길이 $M$ 의 배열이 있을 때, $N$ 번에 걸쳐
- $C[j]$ 번 색을 칠할 수 있는 일꾼 $i$ 들에 대해서 $A[(i-j)\%m]++$
- 그 외에 대해서 $0$ 으로 초기화
이라는 연산을 효율적으로 구현해야 한다. 첫 번째는 그러한 엔트리가 650개 이하니까 그냥 해 주면 된다. 두 번째는 해 줄 수가 없으니, 마지막으로 해당 엔트리가 갱신된 시점을 추가 배열을 둬 기록하자. 만약에 첫 번째 연산을 할 때, 마지막으로 해당 엔트리가 갱신된 시점이 직전 ($j-1$) 이 아니라면, 0이라고 간주하고 그 때 덮어씌워주면 된다.
마지막으로, $(*, y)$ 형태의 지령이 있는지는 $DP[i][j]$ 에 $m$ 이상의 엔트리가 있는지를 확인하면 된다. 위에서 봤듯이 $DP[i][j]$ 에서 0이 아닌 엔트리는 많아야 650개이고 전부 열거할 수 있으니, 이 과정에서 확인해 주면 된다.
시간 복잡도는 $O(N \sqrt{400000})$ 이다.
2. 자매 도시
Subtask 3 (30점)
쿼리와 가중치 최대화를 무시하고, 그래프가 주어졌을 때 두 정점 $u, v$ 간에 자매를 맺을 수 있는 조건이 무엇인지 살펴보자. 몇 가지 관찰을 할 수 있다.
- 먼저, 그래프 상에서 $u, v$ 는 연결되어 있어야 한다.
- 둘이 속한 컴포넌트에 사이클이 있다면 자매를 맺을 수 있다. 사이클 상의 서로 다른 두 정점으로 $u, v$ 를 옮겨 주자 (사이클에 가까운 정점을 먼저 옮기면서 겹치지 않게 하자). 이제 둘이 같이 시계방향으로 한 바퀴 돌면서 서로의 자리를 바꾼다. 이제 처음 사이클에 올 때 왔던 길로 돌아가면 된다.
- 둘이 속한 컴포넌트에 degree 3 이상의 정점이 있다면 자매를 맺을 수 있다. 해당 정점에 인접한 세 정점을 ${a, b, c}$라고 하자. 만약에 $u, v$ 에서 해당 세 정점 중 하나로 겹치지 않으면서 갈 수 있으면 그렇게 가자. 그렇지 않다면 특정 정점 $a$ 에 병목이 걸리는 건데, $a$ 에 가까운 쪽이 먼저 출발해서 $b$ 로 들어가고, 그 다음에 출발한 쪽이 $c$ 로 들어가면 된다. 이제 마치 swap 함수를 구현하듯이, 남은 한 쪽 정점을 보조 위치로 두고, 둘의 위치를 바꾼 후, 왔던 길로 돌아가면 된다.
세 조건 모두에 해당이 안 되는 경우를 살펴보자. 이 경우 $u, v$ 는 연결되어 있으며, 해당 컴포넌트는 트리고 (사이클이 없음), 차수 3 이상의 정점이 없다. 고로 $u, v$ 는 일직선 위에 놓여 있는 것이다. 이 경우에는 둘이 자매를 맺을 수 없음을 보일 수 있다. 이로서 자매를 맺을 수 있는 조건을 쉽게 판단할 수 있다.
서브태스크 3에서는, 각 쿼리를 모두 개별적으로 처리한 후, 각 쿼리마다 최대 용량의 상한 $X$ 를 둔 다음에, 해당 상한 이하의 간선들만 모았을 때 위 조건이 만족하는지를 DFS/BFS로 판단하면 된다. 상한 $X$ 를 모든 정수에 대해 다 해 봐야 하나 싶을 수 있으나, 결국 문제의 정답은 특정 간선의 가중치랑 일치할 것이기 때문에, 각 간선들을 가중치 오름차순으로 정렬한 후, $W[0], W[1], \ldots, W[m-1]$ 만 상한으로 시도해 보면 된다. $O(QM^2)$ 시간 복잡도에 문제를 해결할 수 있다.
서브태스크 1과 2는 이 관찰, 혹은 그 중 일부를 응용하면 된다. 서브태스크 1은 입력이 사이클이거나 일직선이다. 고로 각 사이클에 대해서 간선의 최댓값과 함께 Flood-fill을 해 주면 된다. 서브태스크 2는 입력이 성게이다. $X[j] = 0$ 인지 아닌지에 따라 적당한 케이스 처리로 해결할 수 있다. 자세한 설명은 생략한다.
Subtask 4 (50점)
최대 용량의 상한 $X$ 에 대해서 이분 탐색을 할 수 있어서, $O(QM \log M)$ 으로 최적화할 수 있다.
Subtask 5 (73점)
특별히 만점 풀이보다 쉬운지는 모르겠다.
서브태스크 5에서는 그래프가 트리이기 때문에 사이클 조건을 볼 필요가 없다. $MaxPath(u, v)$ 를 두 정점 $u, v$ 간의 트리 상 경로 최댓값이라고 하자. $u, v$ 를 연결시키기 위해서는, 상한이 $MaxPath(u, v)$ 보다는 커야 한다.
여기에 degree 3 이상의 정점을 추가해야 하는데, 이 정점을 $x$ 라고 고정하자. $x$ 의 degree가 3 이상이 되기 위해서는, 현재 상한이 $x$에 인접한 간선 중 가중치가 세 번째로 작은 간선보다 커야 한다. 이 상한을 $Limit[x]$ 라고 하자. 각 쿼리마다 우리가 구해야 하는 것은:
$min_x(max(Limit[x], MaxPath(x, u), MaxPath(x, v)))$
이 식을, $x$ 에서 경로 방향으로 뿌려주는 식으로 최적화하자. $Dist[x]$ 를, $x$ 라는 정점에서 degree 3인 정점을 도달하기 위한 최소 상한이라고 정의하자. $Dist[x]$ 는 Dijkstra’s algorithm을 사용해서 해결할 수 있다. 모든 $Limit[x]$ 를 우선순위 큐에 넣은 후, 인접한 정점으로 전이될 때 $Dist[y] = min(Dist[y], max(Dist[x], w(u, v)))$ 와 같은 식으로 relaxation을 해 줄 수 있기 때문이다. 이 전처리는 $O(n \log n)$ 시간에 가능하다.
이제 전처리가 끝났다면, 문제의 정답은 $max(min_{x \in path(u, v)} Dist[x], MaxPath(u, v))$ 이다. 이 두 값은 모두 Sparse table을 통해서 구할 수 있다. 사실은, 이를 더 간단하게 써서 $max(Dist[u], MaxPath(u, v))$ 로 써도 된다. 시간 복잡도는 $O((n + q) \log n)$이다.
만점 풀이 (100점)
각 쿼리마다, 답에 대한 이진 탐색을 사용하자. 우리는 간선들의 prefix에 대해서, 해당 prefix만으로 그래프를 이루었을 때 위 조건이 만족하는지를 아주 빠르게 알고 싶다. 이를 위해서는 간선의 prefix에 대한 연결성 등의 정보를 저장해야 하는데, 어떤 식으로 할 수 있을까?
먼저, 위에서 설명한 조건들은 그래프 탐색만이 아니라 Union-find를 사용해서도 판별할 수 있다. 첫 번째 조건은 굉장히 자명하게 판별할 수 있다. 두 번째 조건은, 그래프에 간선이 하나 추가될 때, 차수가 3 이상이 되는 정점이 있으면 해당 정점이 속한 컴포넌트에 “이 컴포넌트 안에 가중치 3 이상의 정점이 있음” 이라고 적어주자. 세 번째 조건은, 같은 컴포넌트를 잇는 간선이 들어오면 해당 컴포넌트에 사이클이 있다고 라벨링을 하는 식으로 처리할 수 있다.
우리는 간선들의 prefix들이 조건을 만족하는지를 빠르게 판별하고 싶다. 이 때 위에서 설명한 방식으로 UF를 관리하면, 각 prefix에 대해서 필요한 자료구조를 구성할 수 있다. 하지만, 쿼리가 온라인이라서, 이렇게 구성한 자료구조를 각 쿼리마다 제공할 수는 없다.
이 점을 해결하기 위해서 UF를 Persistent하게 관리하자. 모든 정점들에 대해서, 해당 정점에 대한 정보를 하나의 값으로 저장하지 않고, 값들의 리스트로 저장하자. 이 리스트는 (해당 값이 갱신된 시점, 갱신된 후의 값) 을 시간순으로 저장하면서, UF에 존재했던 모든 역사를 기록한다. UF의 정보를 변경해야 한다면, 어떠한 값을 덮어씌워주는 대신에, 새로운 갱신을 리스트에 넣어준다.
이제 다시 돌아와서, 각 쿼리마다 답에 대한 이진 탐색을 사용하자. 특정 prefix $[0, i - 1]$ 에 대해서, $u, v$ 가 자매를 맺을 수 있는지 아는 것은 일반적인 UF랑 똑같이 하면 된다. 다만 차이점은, $i$ 번 이후의 갱신을 모두 무시하고 싶기 때문에, $i$번 이전에 갱신된 가장 최신의 정보만을 사용해야 한다는 것이다. 이는 리스트에 대한 이진 탐색으로 찾을 수 있다.
이제 시간 복잡도를 생각해 보자. 일단 Path compression은 이 문제에서 적절하지 않다. 쿼리에서 Find를 할 때는 path compression이 불가능하고 최악의 경우 $O(n)$ 연산이 필요할 수 있기 때문이다. 사실 Rank compression도 $\log n$ 개의 노드를 봐야한다는 것이 부담스럽다. 구현하기도 귀찮을 것 같다. 제일 좋은 것은, 두 노드를 합칠 때, 컴포넌트 크기가 작은 쪽을 직접 순회하면서 변형하고, Find 연산이 $O(1)$ 이 되도록 구현하는 것이다. 흔히 말하는 small-to-large를 직접적으로 구현한다고 생각하면 된다. 이렇게 구현하였다면,
- 초기화 $O(m \log n)$
- 각 쿼리마다 이진 탐색 후 Find 연산으로 판별: 이진 탐색에 $O(\log n)$, Find 연산이 참조하는 노드 $O(1)$, 노드 참조에 $O(\log n)$
이 되어서 $O(m \log n + q \log^2 n)$ 에 문제가 해결된다.
3. 즐거운 행로
Subtask 1 (10점)
서브태스크 1/2에서는, $N^2$ 번의 쿼리로 전체 트리를 찾을 수 있다. 모든 정점 쌍을 열거한 뒤, 거리가 1인 두 정점 사이에 간선을 추가해 주면 되기 때문이다. 고로 트리가 주어진다고 가정한다.
정확히 이 서브태스크의 의도가 무엇인지는 잘 모르겠다. Subtask 1은 풀지만 2는 못 푸는 풀이로는 Bitmask DP를 사용하는 풀이가 있다. $DP[S][u][v]$ = (방문한 정점 리스트가 ${\ldots, u, v}$ 꼴이며, 이를 집합으로 뒀을 때 $S$ 라면, 답이 존재하는가?) 로 정의하면, $O(2^n n^3)$ 정도에 문제를 해결할 수 있다. 이에 대해서 자세한 설명은 생략한다.
Subtask 2 (26점)
이런저런 관찰을 하다보면 (예를 들어, 직선을 두고 생각하다 보면) 문제에서 하는 첫 이동 이 트리의 지름이면 굉장히 편하다는 것을 알 수 있고, 이것을 더 확장하면 다음과 같은 그리디 알고리즘을 얻을 수 있다: 지름을 구하고, 그 끝점 중 하나에서 시작해서, 가장 먼 방문하지 않은 점을 반복해서 방문하는 것이다. 이를 반복하면 $O(n^2)$ 시간에 문제를 해결할 수 있다. 전체 트리를 찾고 시작해도 되지만, 사실 두 점 간의 거리만 필요하기 때문에 굳이 그렇게 구현할 필요는 없다.
Subtask 3 (47점)
서브태스크 3에서도, 서브태스크 2와 동일하게 가장 먼 방문하지 않은 점을 반복할 것이다. 다만 서브태스크 2처럼 그대로 하면 $O(n^2)$ 시간과 쿼리 횟수가 필요하기 때문에 개선이 필요하다.
첫 번째로 관찰해야 할 것은, 서브태스크 3을 풀 때는 쿼리라는 것이 전혀(!) 필요하지 않다는 것이다. 그냥 문제 지문에 트리가 어떤 식으로 생겼는지 잘 적혀있기 때문에, 그러한 트리를 그냥 사용하면 된다 (…) 이제 쿼리에 관한 이야기는 하지 않고, 트리가 알려져 있다고 가정하고 문제를 해결한다.
두 번째로 관찰해야 할 것은, 트리의 깊이가 작다는 것이다. 이를 활용해서 위의 그리디 알고리즘을 $O(n \times \log n)$ 으로 최적화할 수 있다. $DP[v]$ = ($v$ 의 서브트리에서 방문할 수 있는 가장 깊은 정점) 를 저장한다. 현재 있는 정점에서 가장 먼 정점을 찾는 것은, 현재 정점과 방문할 정점의 LCA를 고정한 후, 이에 따라서 $\log N$ 개의 DP 값을 보면 된다. 어떠한 정점을 방문했다고 마크한다면, 해당 정점과 해당 정점의 모든 조상들에 대해서만 DP값이 바뀐다. 고로 이러한 $\log N$ 개의 정점들에 대해서만 bottom-up으로 DP값을 갱신해 주면 된다.
만점 풀이
서브태스크 4의 설명은 복잡하지만, 결국 루트 $T$에서의 최대 깊이가 30 미만이며, 각 정점이 중위순회 (inorder) 로 번호가 매겨짐이 보장되는 서브태스크이다. 점수가 19점 밖에 안 되지만 풀기가 아주 까다로운 것 같다. 내 생각에는, 루트 정점을 찾으면, 루트와의 거리 (depth) 를 $n-1$ 번의 쿼리로 구할 수 있고, 깊이를 알면 재귀적으로 트리 자체도 구할 수 있어서, 서브태스크 3처럼 해결하는 게 풀이인 것 같다. 루트 정점은 어떻게 찾는지 모르겠다 (좋은 방법이 있으면 댓글로 적어주세요!).
하여튼, 지금까지의 모든 풀이는 트리 $T$ 를 알 수 있다는 가정 하에 작동하지만, 일반적인 케이스에도 트리 $T$ 를 알 수 있을 가능성은 낮아 보인다. 또한, 지금까지 사용한 그리디 알고리즘을 일반적인 케이스에서 적용할 수 있을 가능성도 낮아 보인다. 이 문제는 트리가 전부 다 주어져도 $O(n \log n)$ 에 풀기 힘든 문제 이기 때문이다. 그게 정해라면 하여튼 등수 걱정은 안 해도 될 것 같다. 고로 처음 생각한 것과 다른 형태의, 조금 더 찾기 쉬운 construction을 생각해야 한다.
직선인 케이스를 생각해 보면, 처음에는 직선의 양 끝에서 시작하다가 결국에는 직선의 중심에서 끝난다. 역으로, 직선의 중심에서 시작해서 뻗어나가는 풀이를 생각해 보자. 트리에는 크게 두 가지 중심이 있는데, 바로 Center와 Centroid이다. 첫 번째는 지름의 중점이고, 두 번째는 제거했을 때 남는 서브트리의 크기가 $n/2$ 이하이게 하는 정점이다. 몇 가지 시도를 해 보면, 문제를 해결하기에는 Centroid가 더 적합하다는 사실을 직감할 수 있다.
Centroid는 어떻게 구할까? 일반적으로 Centroid의 존재를 증명하는 방식은, 임의의 정점에서 시작해서 서브트리 크기가 $n/2$ 이하인 정점 방향으로 계속 움직이는 것이다. 트리의 루트를 0번 정점으로 둔 후, 서브트리 크기가 큰 방향으로 계속 내려가자. 이것이 멈추는 지점(centroid) $c$ 에서는, 모든 서브트리가 $n/2$ 이하이다. 고로 AttractionsBehind(0, c) 는 $n/2$ 이상이다. $T$ 에서 AttractionsBehind(0, c) 가 $n/2$ 이상인 정점들은 모두 $c$ 혹은 그의 조상들이다. 고로 $c$ 는 그들 중 값이 최소인 정점이 된다. 이렇게 하면 AttractionsBehind(0, i) 함수를 $n$ 번 호출함으로써 centroid를 쉽게 찾을 수 있다. 이제 루트를 Centroid로 잡고 이야기를 다시 시작하자.
Centroid를 지웠을 때, 2개의 서브트리가 나왔다고 생각해 보자. 모든 서브트리의 크기가 $n/2$ 이하니까, 두 서브트리의 크기 차는 1이다. 서로 다른 서브트리에 속하는 두 정점 $x, y$ 에 대해서, 둘 간의 거리는 $dist(x, c) + dist(y, c)$ 가 된다. 이 값을 계속 줄이면서, 교대로 각 서브트리에서 정점을 골라야 한다. 이는 두 서브트리에 대해서, 모든 정점을 centroid와의 거리 기준으로 정렬한 후, $dist(c, x)$ 가 최대인 점을 교대로 뽑아주면 된다. 크기 차가 1이니, 가장 큰 곳에서부터 시작하면 된다. 이렇게 되면, $x_1 + y_1 \le x_1 + y_2 \le x_2 + y_2 \le \ldots$ 같은 느낌으로 거리가 계속 줄어듬을 알 수 있고, 문제가 해결된다.
이제 3개의 서브트리가 나왔다고 생각해 보자. 위 접근을 그대로 취하면, 맨 처음에 $c$ 에서 가장 먼 점에서 시작한 후, 현재 서브트리와 다른 서브트리이면서 가장 먼 점으로 움직이는 것을 반복할 수 있다. 이 접근을 취하면 항상 각 이동에서의 거리는 감소하지만, 이렇게 하면 끝날 때 모든 정점을 방문하지 않을 수 있다. 각 서브트리에 정점이 (10, 10, 10) 개 있는데, 두 개의 서브트리에 먼 정점이 너무 많아서, 이들을 모두 방문한 후 남은 서브트리를 방문했다고 하자. 그렇게 되면 각 서브트리에 정점이 (1, 1, 10) 개 있게 되고, 다른 서브트리 조건을 만족하면서 이들을 원하는 대로 방문할 수는 없다.
거리 조건을 만족시키면서 서브트리 조건을 불만족시키는 것과 반대 극단으로, 거리 조건을 불만족시키면서 서브트리 조건을 만족시키는 것을 생각해 보자. Centroid 조건의 특징은, 거리를 감안하지 않는다고 하면 항상 서로 다른 서브트리만 왔다갔다 하는 투어를 찾을 수 있다는 것이다. 달리 말해, 다음과 같은 Lemma가 성립한다. (사실, 이 결론 자체는 색이 3개 초과여도 증명 가능하다.)
- Lemma. 빨간색, 파란색, 초록색 구슬이 각각 $r, g, b$ 개 있을 때, $max(r, g, b) \le \lceil (r + g + b) / 2 \rceil$ 인 것과, 인접한 구슬이 서로 다른 색이 되도록 일렬로 나열할 수 있음이 필요충분이다.
- Proof sketch. 역방향은 비둘기집의 원리에 의해 자명하다. 정방향은, $max(r, g, b) < \lceil (r + g + b) / 2 \rceil$ 이 만족할 때 까지 빨/파/초 구슬을 순서대로 뽑다가 (이 때 항상 $r > 0, g > 0, b > 0$ 이 성립함을 관찰하자), 등식이 성립하는 순간, 가장 자주 등장하는 색을 홀수번째 위치에 놓고, 다른 색을 짝수번째 위치에 놓는 식으로 번갈아 배치하면 된다.
이제 위에서 사용한 알고리즘을 조금만 변형해 보자. 맨 처음에 $c$ 에서 가장 먼 점에서 시작한 후, 현재 서브트리와 다른 서브트리이면서 가장 먼 점으로 움직이는 것을 반복한다 (1단계). 그러다가 어떠한 서브트리의 크기가 전체 정점 개수의 반을 초과하게 되면, 더 이상 이를 반복할 수가 없다. 이 때, 작은 두 서브트리를 합쳐준 후, 두 개의 서브트리의 케이스를 풀듯이 남은 문제를 해결하자. (2단계)
이 알고리즘은 1단계와 2단계 각각에서는 거리가 계속 줄어든다. 이제 문제점은 1단계에서 2단계로 넘어가는 그 순간에 있다. 이런 저런 케이스를 해 보면, 가장 먼 점으로 움직였다 는 조건 때문에 웬만한 경우 별다른 문제가 없이 거리가 계속 감소한다는 조건을 유지할 수 있고, 아니라 하더라도 약간의 수정만 하면 다 고칠 수 있다. 알고리즘의 개략적인 흐름은 이것으로 끝이다.
이제 이 알고리즘을 구현해야 한다. 1단계와 2단계 과정을 구현하는 것은 어렵지 않지만, 1단계에서 2단계로 넘어가는 순간에 고려해야 할 것이 상당히 많다. 이 부분이 이 문제에서 가장 짜증나는 부분이다. 나는 이것을 해결하는 쉬운 방법은 잘 생각이 나지 않았고, 직접 따져보는 건 너무나도 하기 싫었다. 이 때, 문제에서 주는 sample grader를 사용하면 굉장히 유용하다. Sample grader를 조금만 변형하면, 여러 랜덤 데이터에 대해서 stress test를 매우 쉽게 돌려볼 수 있다. 랜덤한 이진 트리를 만드는 것은, 노드 $i$ 에 대해서 $[0, i - 1]$ 구간에 있는 degree 2 이하의 랜덤한 정점을 골라주는 식으로 할 수 있다. 고로 위와 같은 알고리즘을 짜고, 적당히 반례를 찾은 후, 각각의 반례에 대해서 ad-hoc하게 수정을 반복하는 식의 땜질 (…) 로 충분히 만점을 받을 수 있다. 내가 반례를 찾으면서 코드에 넣은 ad-hoc한 수정들은 대략 이런 것들이 있다.
- 1단계를 탈출할 때는, 마지막으로 방문한 노드가 현재 방문한 모든 노드 중 거리가 최대인 것이 유용하다. 현재 방문한 노드보다 거리가 큰 노드가 존재한다면, 1단계를 일단 탈출하지 말자.
- 2단계에서 처음 시작하는 노드는 거리가 최대여야 한다. 만약에 거리가 최대인 모든 노드가 현재 서브트리와 같다면, 그 때는 아무래도 상관이 없다.
- 마지막 정점이 centroid라는 사실을 적절히 활용하면 2단계를 오차 없이 수월하게 끝낼 수 있다. 작은 쪽에 centroid를 붙여 주면 되기 때문이다.
- comparator 등을 구현할 때 최대한 이미 방문한 서브트리들을 피하는 식으로 구현하자.