티스토리 뷰
문제: 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] Dreaming 해법 (2) | 2013.07.22 |
- Total
- Today
- Yesterday
- Divide & Conquer
- z-trening
- vote
- Boyer-Moore Majority Vote Algorithm
- ioi
- Knuth Optimization
- HackerRank
- Segment tree
- Tree
- IOI2011
- Boyer
- moore
- IOI2013
- dynamic programming
- Splay Tree
- idea
- IOI2012
- Dijkstra
- BOI 2001
- IOI2014
- optimization
- BOI 2009
- BOI
- Algorithm
- Dynamic Pramming
- TRIE
- Greedy Method
- Parametric Search
- USACO
- majority
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |