티스토리 뷰

IOI/IOI2014

[IOI2014 Day1] Game 해법

전명우 2014. 7. 17. 02:14

여러 가지 다양한 해법이 있다고 생각한다.


$0$번 도시 부터 $N-1$번 도시까지 총 $N$개의 도시가 있다. 이 $N$개의 도시들을 단말 노드로 갖는 이진 트리를 만든다. 이 이진트리의 단말 노드의 개수는 정확히 $N$개이다. 이제 모든 $(i,j)$ 쌍 ($0 \leq i < j \leq N-1$)에 대하여 단말 노드 $i$와 단말 노드 $j$의 LCA(Lowest Common Ancestor, 최저 공통 조상)를 $k$라 했을 때, left[k]에 1을 더한다.


쿼리(질문)가 $(u,v)$으로 주어졌을 때, 단말 노드 $u$와 단말 노드 $v$의 LCA를 $w$라 했을 때, left[w] 값을 1 감소 시키고, 그 값이 0 이면, 값을 1 반환하고 감소한 뒤 그 값이 여전히 0 보다 크다면 0을 반환한다.


이런 일련의 알고리즘으로 질문에 대한 답을 하였을 때, 그래프가 연결 그래프임도 증명이 되고, 마지막 질문 전에는 그래프가 연결 그래프가 안됨이 증명된다.


처음 전처리로 이진 트리를 구성하고 모든 $(i,j)$ 쌍에 대한 LCA도 구해 놓는다. 이 때 걸리는 시간복잡도는 $O(N^2 lg N)$ 이다. 쿼리에 대해 답을 계산하는 시간복잡도는 $O(1)$ 이다. 따라서, 문제를 해결하기 위한 전체 시간복잡도는 $O(N^2 lg N)$ 이다.



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

[IOI2014 Day2] Gondola 해법  (0) 2014.07.17
IOI2014 Day 2 종료  (0) 2014.07.17
[IOI2014 Day1] Rail 해법  (0) 2014.07.17
[IOI2014 Day1] Wall 해법  (0) 2014.07.17
IOI2014  (0) 2014.07.17
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
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
31
글 보관함