PS 이야기

문제 ↓ 상당히 까다로워 보이는 문제다. 대회 당시 만점자가 많지 않지만 매우 어려운 문제에 속하진 않는다. 문제는 2차원으로 되어 있지만, 1차원인 경우 부터 먼저 생각해보자. 1차원인 경우 각 셀들이 모두 연결되어 있어야하므로, 셀들이 일직선으로 연결되어있는 선분 하나만 존재할 것이다. 이 때 각 셀 쌍들이 이동하는 거리는 $|X_i-X_j|$ 이다. 이런 셀들이 N개 있을 때 O(N lg N) 정렬 후, O(N) 만에 각 셀 쌍들의 거리 합을 구해줄 수 있다. 전체 해법 설명에 앞서, 서브태스크 3 푸는 법을 먼저 소개하겠다. 서브태스크 3에 있는 조건들이라면 각 셀 쌍들의 이동 거리는 1차원일 때와 비슷하게 $|X_i-X_j|+|Y_i-Y_j|$ 이다. 이때 x 좌표의 거리와 y 좌표의 거리를 독..

문제 ↓이 문제를 풀기 위해서 꼭 해야되는 것이 존재한다. 바로, 레오나르도의 최적 전략을 코딩하는 것이다. 레오나르도의 최적 전략에 대한 설명은 문제에 적혀있다. 레오나르도의 최적 전략을 O(N lg K) 만에 해결할 수 있어야한다. O(N) 만에 각 물감이 다음에 같은 종류의 물감이 언제 등장하는지를 계산할 수 있다. 그 이후, 힙(heap)이나 우선 순위 큐(priority queue) 자료구조를 이용하면 O(N lg K)만에 해결 가능하다.서브태스크 1,2,3 그리고 서브태스크 5의 부분 점수를 노리는 방법은 직관적으로 생각할 수 있다. 각 Request 별로 비계에서 PutBack 해야되는 물감의 번호를 비트로 넘겨주면 된다. 각 Request 별로 차지하는 비트 수는 lg N 이다. 따라서 서..

문제 ↓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..