[IOI2012 Day2] Super 해법

문제 ↓

super.pdf

이 문제를 풀기 위해서 꼭 해야되는 것이 존재한다. 바로, 레오나르도의 최적 전략을 코딩하는 것이다. 레오나르도의 최적 전략에 대한 설명은 문제에 적혀있다. 레오나르도의 최적 전략을 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