티스토리 뷰

IOI/IOI2012

[IOI2012 Day1] Scrivener 해법

전명우 2013.07.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
[IOI2012 Day1] Scrivener 해법  (0) 2013.07.22
댓글
댓글쓰기 폼