PS 이야기

공식 홈페이지: http://www.ioi2013.org 결과: http://ioi.eduardische.com/results/2013대회 페이지: http://compete.ioi2013.org/IOI2013 은 외부인에 대한 배려도 괜찮은 편이다. 시험이 끝난지 보름이 다 되어가는 지금까지도 대회 페이지를 열어놓고 채점을 할 수 있게 해놓는다. 대회 페이지에 들어가면 페이스북, 트위터, 구글 계정으로 로그인해서 사용할 수 있게 되어있어 편하다. 다만 아쉬운 점이 있다면, task implementation을 공식 홈페이지에 게재하지 않아 찾느라 헤매게 되었다.IOI 예비 참가자들이 대회 환경이 어떻게 구성되어 있는지 확인할 수 있는 좋은 기회로 여겨진다.

문제 ↓ 문제의 고리를 노드로 고리끼리 연결이 되면 간선으로 연결을 해주어 그래프로 표현할 수 있다. 문제의 해법에 접근하기 위해서는 다음과 같은 사실들을 관찰할 필요가 있다. 만약 차수가 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..