티스토리 뷰
문제 ↓
이 문제를 풀기 위해서 꼭 해야되는 것이 존재한다. 바로, 레오나르도의 최적 전략을 코딩하는 것이다. 레오나르도의 최적 전략에 대한 설명은 문제에 적혀있다. 레오나르도의 최적 전략을 O(N lg K) 만에 해결할 수 있어야한다. O(N) 만에 각 물감이 다음에 같은 종류의 물감이 언제 등장하는지를 계산할 수 있다. 그 이후, 힙(heap)이나 우선 순위 큐(priority queue) 자료구조를 이용하면 O(N lg K)만에 해결 가능하다.
서브태스크 1,2,3 그리고 서브태스크 5의 부분 점수를 노리는 방법은 직관적으로 생각할 수 있다. 각 Request 별로 비계에서 PutBack 해야되는 물감의 번호를 비트로 넘겨주면 된다. 각 Request 별로 차지하는 비트 수는 lg N 이다. 따라서 서브태스크 1,2는 해결이 된다. 서브태스크 3은 조금 다르게 풀어야하는데, Request 별로 PutBack 해야되는 물감의 번호가 아닌 비계에서 몇 번째 물감을 빼야하는지 비트로 저장하면 된다.
서브태스크 4와 서브태스크 5를 만점 받기 위해서는 비트를 N+K 개 사용해야한다. Request 별로 lg N 개의 비트를 전하는 기존의 방법에서 Request 별로 비트를 오직 1개 써야하는 해법을 생각하기는 쉽지 않다. 처음 K개의 비트는 0번 물감부터 K-1번 물감까지 비계에 남아있지 않아도 되는 물감인지를 의미한다. 그리고 이후 N개의 비트 또한 마찬가지다. 물감이 비계에 꼭 남아 있어야하는지, PutBack 해도 되는지를 의미한다. advisor.cpp에서 레오나르도의 전략을 실행할 때 어떤 물감이 다음에 같은 종류의 물감이 등장하기 전에 비계에서 PutBack 되어 진다면, 이 물감은 비계에서 꼭 PutBack 되어야하며, 어느 순간이든 상관 없이 비계에서 PutBack 되어도 된다는 이론이다. assistant.cpp 에서 Request 마다 체크된 물감 아무 것이나 PutBack 하면 된다.
코드(advisor.cpp): http://ideone.com/1gTg6v
코드(assistant.cpp): http://ideone.com/AV17qU
'IOI > IOI2012' 카테고리의 다른 글
[IOI2012 Day2] City 해법 (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 |
- Total
- Today
- Yesterday
- z-trening
- Tree
- TRIE
- Parametric Search
- BOI 2001
- dynamic programming
- ioi
- Divide & Conquer
- Algorithm
- majority
- BOI
- Dynamic Pramming
- Knuth Optimization
- Boyer
- moore
- optimization
- Greedy Method
- IOI2012
- IOI2013
- IOI2011
- Segment tree
- vote
- IOI2014
- HackerRank
- Boyer-Moore Majority Vote Algorithm
- USACO
- idea
- BOI 2009
- Dijkstra
- Splay Tree
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |