티스토리 뷰
문제 ↓
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)를 해결할 수 있다.
'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
링크
TAG
- Greedy Method
- Algorithm
- dynamic programming
- moore
- ioi
- Dynamic Pramming
- Boyer-Moore Majority Vote Algorithm
- IOI2011
- Splay Tree
- IOI2013
- HackerRank
- z-trening
- Parametric Search
- IOI2012
- BOI
- BOI 2009
- Knuth Optimization
- Boyer
- Tree
- TRIE
- Dijkstra
- idea
- optimization
- vote
- Divide & Conquer
- IOI2014
- BOI 2001
- Segment tree
- majority
- USACO
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함