티스토리 뷰

IOI/IOI2013

[IOI2013 Day1] Wombats 해법

전명우 2013.07.22 01:39

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day1/wombats/Wombats ko (KOR).pdf

상당히 까다로운 문제다.
이 문제의 해법은 $C$ 값이 $R$ 값에 비해 상대적으로 작다는 사실에서부터 시작한다.

행 X와 행 Y가 있을 때 행 X의 어느 점에서 행 Y의 어느 점으로 가는 $C^2$가지 경우에 대해 사전계산(precompute) 할 수 있다. {X,Y} 를 사전계산 해놓은 것이라 하자. {X,Y}와 {Y,Z}를 합쳐 {X,Z}를 만들 수 있다. 간단하게 합치는 시간복잡도는 $O(C^3)$이지만, Knith-Optimization과 비슷한 방법으로 $O(C^2)$ 시간복잡도를 갖으며 합칠 수 있다. 이를 위해서는 한 가지 중요한 아이디어가 필요하다. 최적 경로가 (X,i)에서 (Z,j-1)로 (Y,p)를 거쳐가고, (X,i+1)에서 (Z,j)로 (Y,q)를 거쳐간다고 하자. 이 때 (X,i)에서 (Z,j)로 가는 최적경로가 (Y,r)을 거쳐간다면 $p \leq r \leq q$ 이다. 이 아이디어는 최적 경로들은 서로 교차하지 않다는데에서 나온다. 쉽게 증명가능하다. 이 사실을 이용하여 j-i 가 증가하는 순서로 $O(C^2)$만에 {X,Y}와 {Y,Z}를 {X,Z}로 합칠 수 있다.

위의 알고리즘과 segment tree를 사용하면 제한시간 내에 문제를 해결할 수 있다. Segment tree의 노드가 [s~e]라면 s번 행에서 e+1번 행까지 가는 $C^2$가지의 전처리된 값들이 있다. Segment tree 구성은 위에서 설명한 방법으로 두 자식 노드를 합치면 된다. 그리고 답을 구하는 것은 segment tree의 루트에 있는 정보를 활용하면 되므로, O(1) 시간복잡도를 갖는다. update 하는데 시간복잡도는 위에서 설명한 방법으로 $O(C^2 \lg R)$ 이 된다.

다만 트리의 정점 개수가 많아 메모리제한을 초과한다. 여기까지하면 76점을 받을 수 있다. 76점에서 100점으로 점수를 끌어올리는 방법은 간단하다. 시간제한이 20초로 매우 넉넉하기 때문에 segment tree의 단말 정점의 구간 크기를 늘려주면 된다. 기존 방법에서 단말 정점의 구간이 [x~x] 라면 [x~x+20] 정도로 늘려주면 된다. 이 때 시간은 기존보다 3배정도 더 걸리며, 시간복잡도에서 상수만 커질 뿐 차수는 변하지 않는다.

코드 보기


신고

'IOI > IOI2013' 카테고리의 다른 글

IOI2013 잡담  (2) 2013.07.22
[IOI2013 Day2] Game 해법  (2) 2013.07.22
[IOI2013 Day2] Robots 해법  (0) 2013.07.22
[IOI2013 Day2] Cave 해법  (0) 2013.07.22
[IOI2013 Day1] Wombats 해법  (0) 2013.07.22
[IOI2013 Day1] Dreaming 해법  (2) 2013.07.22
댓글
댓글쓰기 폼