티스토리 뷰

IOI/IOI2012

[IOI2012 Day1] Scrivener 해법

전명우 2013. 7. 22. 04:05

문제 ↓

scrivener.pdf

IOI2012에서 만점자가 가장 많은 쉬운 문제다.

TRIE를 만들어 해결할 수 있다. TRIE의 각 노드는 상황을 의미한다. 하지만 상황을 문자열로 가지고 있지 않는다. Undo는 각 step을 배열을 이용해 노드를 가지고 있으면 하기 쉽다. TypeLetter(L)과 UndoCommands(U)는 O(1)만에 해결이 가능하다.

조금 까다로운 편이 GetLetter(P)인데, TRIE의 각 노드에 문자열을 가지고 있으면 당연히 기하급수적인 공간복잡도를 갖게 된다. 그래서 트리에서 최저공통조상 찾는 알고리즘과 같은 방법으로 $2^i$번 앞에 있는 노드를 배열로 가지고 있으면 된다. 각 노드별로 $lg Q = 20$의 공간복잡도를 사용하며, $O(lg L), L=문자열 길이$ 만에 GetLetter(P)를 해결할 수 있다.

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

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

[IOI2012 Day2] City 해법  (0) 2013.07.23
[IOI2012 Day2] Super 해법  (0) 2013.07.23
[IOI2012 Day2] Tournament 해법  (0) 2013.07.22
[IOI2012 Day1] Rings 해법  (2) 2013.07.22
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
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
글 보관함