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 이다. 따라서 서..

문제 ↓순서대로 라운드가 진행된다. 라운드 (S[i],E[i])가 진행 되면, 구간 (S[i],E[i])에 있던 실력이 제일 좋은 기사만 남고 나머지는 지워진다. 이렇게 한 명의 기사만 남을 때 까지 라운드는 진행된다.프로그램 수행 시간을 좀 더 줄이기 위해서, 기사를 지우지 않아도 된다. 라운드에서 살아남는 기사는 가장 실력이 좋은 기사다. 기사들이 탈락하고 새로운 라운드의 진행을, 기사들이 탈락하지 않는 라운드 진행으로 바꿀 수 있다. 따라서 매 라운드 (S[i],E[i])가 실제로 의미하는 초기 상태에서의 구간 (S'[i],E'[i])를 구할 수 있다. 이 때, 구간 (S'[i],E'[i]) 들은 서로 포함 관계에 있거나 아예 만나지 않는다. 즉, 교차하지 않는다.우리는 이제 새로운 실력 $R$의 ..

문제 ↓ 문제의 고리를 노드로 고리끼리 연결이 되면 간선으로 연결을 해주어 그래프로 표현할 수 있다. 문제의 해법에 접근하기 위해서는 다음과 같은 사실들을 관찰할 필요가 있다. 만약 차수가 4 이상인 노드가 존재하면, 다른 노드들은 중요한 고리가 될 수 없다. 다른 노드를 제거하면 차수가 3이상인 노드가 남기 때문이다. 같은 의미로 차수가 4이상인 노드가 여러 개면 중요한 고리는 존재하지 않는다. 만약 차수가 3인 노드 $V$가 존재하면, 모든 중요한 고리는 $V$ 혹은 $V$에 연결된 노드들 중에 있다.만약 싸이클이 존재하면, 모든 중요한 고리는 싸이클 안에 있다.만약 그래프가 여러 개의 직선으로 구성되어 있으면, 모든 고리가 중요한 고리다.위 사실들을 이용하여 중요한 고리의 개수를 O(1) 만에 구할..

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