[IOI2011 Day2] Elephants 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/elephants.pdf

대회 당시 이 문제에 상당히 많은 시간을 투자했다. 시간제한이 9초라는 것을 간과하고 단지 N 제한이 크다는 이유 만으로 해법이 $O(N lg N)$ 꼴로 나올 것이라 확신했었다. 부분 점수를 받기 위해 $O(N\sqrt{N})$ 꼴의 방법도 생각해보았지만, 실패했었다.

대회 끝나고 나오자마자 당시 조교로 있었던 권순일 형의 짧은 말로 이 문제의 해법을 깨닫게되었다. 2년이 지난 지금까지도 기억에 남는다.

시간복잡도는 $O(N\sqrt{N})$ 이 맞다. 안된다고 생각할 수 있지만, $\sqrt{N}$ 번의 update 마다 새로 그룹들을 $O(N)$만에 구성해주면된다. 그러면 총 시간복잡도를 $O(N\sqrt{N})$ 이고, 안되는 이유도 해결된다.

혼자서 충분히 생각할 수도 있었다고 생각이 들지만, 저 해법을 듣고 난 이후에 $O(N\sqrt{N})$ 방법에 대해 엄청 감동했었다. $\sqrt{N}$ 번 마다 새로 그룹들을 구성하면 된다는 사실이 너무나도 새로웠다.

본론으로 들어가 $O(N\sqrt{N})$ 방법을 설명하겠다. 우선 코끼리들을 위치 순서대로 나열한 다음에 그룹을 $\sqrt{N}$개로 나눈다. 그러면 $\sqrt{N}$개의 그룹과 각 그룹의 크기는 $\sqrt{N}$이 되어있다. 이 그룹들 사이에서 답을 구할 수 있다.

하나의 그룹 안에서 다음과 같은 정보들이 필요하다. 그룹 안의 코끼리에서부터 사진기를 놓기 시작한다면 그룹을 덮기 위해 몇 개의 사진기가 필요한지와, 이 때 카메라가 어디까지 멀리 찍을 수 있는지를 가지고 있는다. 처음에 그룹을 나누고 그룹별로 정보들을 갱신하는데 드는 시간복잡도는 $O(N)$ 이다.

코끼리의 이동을 두 동작으로 나누어 생각할 수 있다.

1. 코끼리가 제거된다.
2. 코끼리가 추가된다.

코끼리를 제거하는 것과 추가하는 것 각각의 시간복잡도는 $O(\sqrt{N})$ 이다. 그룹내의 배열에서 제거/추가하는데 $O(\sqrt{N})$, 그 배열의 정보를 다시 세팅하는데 $O(N\sqrt{N})$ 의 시간복잡도다.

여러 번의 이동 후 그룹의 크기가 매우 커지거나, 한 그룹이 사라질 수 있다. 대략 $\sqrt{N}$ 번의 이동마다, 새로 그룹들을 구성시켜주면 된다. 한 번 그룹들을 구성 시켜줄 때마다 시간복잡도가 $O(N)$이므로, 이 과정의 총 시간복잡도는 $O(N\sqrt{N})$ 이 된다.

따라서 이 해법의 시간복잡도는 $O(N\sqrt{N})$ 이고 시간제한이 9초라 만점을 받기에 충분하다. 미국의 Wenyu Cao가 97점을 받았는데, 그룹내에서 배열대신 vector를 사용하면 나온다고 한다.

코드: http://ideone.com/SVFZ8z