IOI 2011 풀이 (International Olympiad in Informatics 2011)
작성일 기준 BOJ에서 채점 가능한 문제만 풀어보았습니다.
1번. BOJ 5819 열대 식물원
제 풀이는 $O(N + M \log M + Q)$이지만 공식 풀이는 $O(QN)$입니다.
각 연못을 node로 하고 각 산책로에 대해 아름다운 정도를 가중치로 갖는 edge로 directed graph를 구성합니다. 철수가 한 연못에서 다음 연못으로 이동 중인 상태를 ‘어떤 $u$에서 edge를 거쳐 다음 node $v$로 가는 상태’로 볼 수 있습니다. 즉, 철수의 현재 연못과 상태(어느 연못에서 왔는지)는 하나의 directed edge와 같습니다. 이 때 현재 edge를 거치면 다음으로 갈 수 있는 edge는 반드시 존재하며 유일합니다. 각 방향 edge를 node로 생각하면 다음으로 갈 edge를 후속 노드(successor)로 가지는 후속 노드 그래프(successor node graph)를 얻을 수 있습니다.
우선 각 연못 $i$에서 출발하여 도착점 P에 최초로 도달하는 거리 $cnt[i]$를 그래프 탐색으로 구할 수 있습니다. 도착점 P를 포함하는 cycle이 있는 경우, 이를 구성하는 노드의 개수를 $c$라 하면 어떤 연못 $i$는 $cnt[i]$, $cnt[i]+c$, $cnt[i]+2c$, … 마다 도착점 P를 방문하게 됩니다. $cnt[i]$는 최대 $2m$의 값을 가지므로 $2m$이상의 거리부터는 답이 주기적으로 반복됩니다. 따라서 $cnt$배열과 $c$로 각 query를 $O(1)$에 해결할 수 있습니다. 주의할 점은 도착점 P를 거치는 edge가 두 개가 존재할 수 있어 두 경우를 모두 고려해주어야 합니다. (가장 아름다운 길->두 번째 아름다운 길), (두 번째 아름다운 길->가장 아름다운 길)
2번. BOJ 5820 경주
Centroid decomposition을 이용하여 Divide & Conquer하는 문제입니다. 그래프에 대해 Centroid를 찾아 해당 node를 제거했을 때, 전체 노드 수의 절반이하의 노드를 가지는 부분 그래프들이 생겨나게 됩니다. 우선 시작도시와 끝도시가 서로 다른 부분 그래프에 존재하는 경우, 경로는 반드시 Centroid를 지나게 됩니다. 따라서 모든 node들에 대해 centroid들과의 거리를 그래프탐색으로 $O(N)$에 구해놓은 뒤, 길이가 K인 경로의 수를 $O(N)$에 구할 수 있습니다. 시작도시와 끝도시가 같은 부분 그래프에 존재하는 경우에 대해 분할 정복하여 답을 구하게 되면 전체 $O(N \log N)$에 해결 가능합니다.
3번. BOJ 5821 쌀 창고
어떤 $x$가 주어졌을 때, $x$개의 논을 확보에 필요한 최소 비용을 $cost(x)$라고 합시다. $[1,R]$의 범위에서 $cost(x)$는 증가함수의 성질을 만족합니다. 따라서 $cost(x)$가 $B$이하인 값을 만족하는 $x$들의 upper bound를 구하면 됩니다.$cost(x)$는 전처리를 통해 누적합 배열을 만들어 $O(R)$에 구할 수 있습니다. 따라서 $O(R \log R)$에 해결 가능합니다.
4번. BOJ 5822 악어의 지하 도시
좋은 계획 하에 탈출방에 도달할 수 있는 가장 가까운 거리를 구하는 문제입니다. 각 방을 node로 하는 graph가 있을 때, 각 node $i$에 탈출맵까지 ‘좋은 계획 하에 갈 수 있는’ 최소 거리 $d[i]$를 저장한다면 답은 $d[0]$입니다. 초기에 각 탈출방에 대해서는 0의 값을 저장하고 $d[i]$값이 정해진 방들과 가까운 순으로 갱신해나갑니다. 악어가 막을 수 없는 경로만 찾으면 되므로 각 방에 대해 악어는 최선의 선택을 반드시 막는다고 가정합시다. 그러면 두 번쨰로 탈출방에 가까운 방으로만 가야합니다. 즉, $d[i]$값이 구해진 이웃방들 중 두 번째로 짧은 탈출 시간을 골라 갱신할 수 있습니다. 해당 값을 저장하기 위해 제일 짧은 시간, 두 번째로 짧은 시간을 모두 저장해서 비교해야할 것입니다.
탈출방으로 부터 가장 가까운 방을 찾아 $d[i]$ 값을 갱신하는 과정이 ‘다익스트라’와 굉장히 유사하고 시간복잡도 역시 $O(M \log N)$입니다. 다만 탈출방으로 부터 최단거리를 나타내는 것이 아니기 때문에 방문처리에 유의해야 합니다.
5번. BOJ 5823 코끼리
Bucket을 써서 푸는 문제입니다. Range tree를 응용해서 풀어보려다가 틀린 방법인 걸 뒤늦게 깨달았습니다(…).
코끼리들이 있을 때 필요한 카메라의 수는 카메라의 공간이 낭비되지 않게 코끼리를 카메라 범위의 왼쪽 끝에 붙인 후 greedy하게 $O(N)$에 계산할 수 있습니다. 하지만 코끼리들의 위치가 $O(M)$번 갱신됩니다. 각 코끼리를 순서대로 $k$개식 그룹지어 답을 각각 계산해두고 query마다 합치는 연산을 하여 답을 구한다고 합시다. 위치가 update될 때, 해당 그룹만 update하면 됩니다. 여기서 이 그룹을 나누는 방법을 Bucket을 써서 푼다고 합니다.
query에 대해 합치는 방법은 다음과 같습니다. 각 그룹의 코끼리를 모두 찍었을 때, 마지막 카메라의 남는 범위가 존재합니다. 해당 범위에 오른쪽 그룹의 코끼리가 포함되었다면 해당 코끼리들을 또 찍을 필요가 없습니다. 따라서 다음 그룹에서는 이 코끼리들을 뺀 상태에서의 최소 카메라 수를 계산해야함을 알 수 있습니다. 즉, 각 그룹에 대해 처음$i$개의 코끼리를 제외한 나머지에 대해, 최소 카메라 수와 이 때 카메라의 오른쪽 공간에 남는 범위가 필요합니다. 이는 위에서 언급했듯이 greedy하게 선형 시간 $O(k)$에 구할 수 있습니다. update는 코끼를 빼거나 더하고 해당 그룹만 다시 계산하는 방법이 있습니다. 이 역시 $O(k)$의 시간이 걸립니다.
처음에 모든 그룹에 대해 전처리를 하면, $O(N/k)$의 그룹에 대해 $O(k)$에 구하므로 $O(N)$에 구할 수 있습니다다. 각 query는 모든 그룹에 대해 전처리해둔 값을 이용해 $O(1)$에 카메라 수를 누적하고, 다음 그룹에 대한 시작 범위를 binary search로 $O(\log k)$에 찾을 수 있습니다. 따라서 query처리에 $O((N/k) \cdot \log k)$가 걸립니다. update는 query와 같은 수로 일어나므로 $O(Mk)$. N과 M의 최대값이 같으므로 $O(N) = O(M)$으로 보면, 총 시간복잡도는 $O(N)+O(N(N/k)⋅logk)+O(Nk)$입니다.
단, 코끼리가 추가되고 빠지는 과정에서 편향되게 쌓이는 현상이 일어날 수 있습니다. 한 그룹에만 코끼리가 쌓이면 update될 수록 그룹 크기 k가 $O(N)$으로 늘어나 update에 $O(N)$이 걸려 시간복잡도는 $O(N^2)$으로 늘어날 수 있습니다. update에 걸리는 시간을 $O(N \log k)$로 제한하기 위해 매 $O(k)$번의 호출마다 전처리를 다시하여 그룹의 크기를 $O(k)$로 유지할 수 있습니다. 이 경우 총 시간복잡도는 $O(Nk) + O(N(N/k) \cdot \log k) + O(Nk)$입니다. 그룹의 크기를 $O(N \sqrt{N} \cdot \log \sqrt{N})$에 해결할 수 있습니다.