티스토리 뷰

ICPC/2013 인터넷예선

A. Battleship

전명우 2013. 9. 29. 14:07


ProblemA_Eng.pdf


입력으로 주어지는 두 점 $(x1,y1)$ <--> $(x2,y2)$를 잇는 선분이 있다.

(WLOG 편의상 $x1 \le x2 , y1 \le y2$)

입력으로 주어지는 직선은 수직선이나 수평선이다.

따라서 $x = a$ 꼴의 수직선이 이 선분과 교차하기 위해서는 $x1 \le a \le x2$ 이여야 한다.

$y = b$ 꼴의 수평선이 이 선분과 교차하기 위해서는 $y1 \le b \le y2$ 이여야 한다.


이 관찰을 통해, 이 문제를 indexed tree로 $O(N \lg N)$ 만에 해결할 수 있다.

x좌표의 트리, y좌표의 트리 두 개를 만들어야 하는데, 두 과정이 똑같으므로 x좌표의 트리에 대해서만 설명하겠다.


우선 indexed tree의 각 노드를 stack으로 잡는다.

모든 선분에 대해, 선분이 차지하는 x범위에 해당하는 트리의 노드에 선분을 push한다.

$x = b$ 꼴의 수직선이 주어졌을 때, b를 범위로 갖는 모든 노드의 stack에 있는 선분들을 pop하고 그 중에 최대값을 답으로 출력한다.

pop되는 선분들 중 이미 이전에 제거된 선분이 있을 수 있으므로 크기 N의 visit 배열을 만들어서 visit 체크가 안된 것만 최대값으로 갱신해주면 된다.


이 알고리즘의 시간복잡도가 커 보일 수 있다. 하지만 시간 복잡도는 $O(N \lg N)$ 이다.

까닭은 한 선분이 push되는 노드의 수는 최대 $2 \lg N$ 이다. 마찬가지로 한 선분이 pop최는 회수 또한 최대 $2 \lg N$ 이다.

push와 pop은 $O(1)$(constant time complexity) 이므로 전체 $O(N \lg N)$의 시간복잡도를 갖는다.


후문: 대회 당시에는 정신없고 빨리 풀어야된다는 조급함에 list로 push, pop을 안하고 불필요하게 Priority Queue를 사용해서 $O(N \lg^2 N)$에 해결했다..


A.cpp



'ICPC > 2013 인터넷예선' 카테고리의 다른 글

F. KCPC  (0) 2013.09.29
E. Falling Ants  (0) 2013.09.29
D. 이중 우선순위 큐  (1) 2013.09.29
C. Casting  (0) 2013.09.29
B. 카잉 달력  (0) 2013.09.29
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
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
글 보관함