PS 이야기

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/race.pdf이 문제는 분할정복기법(Divide & Conquer)로 풀 수 있다. 노드 v를 선택하고 v를 포함한 길이가 K인 경로 중 가장 짧은 경로를 찾는다. 그리고 노드 v를 제거한다. 남은 트리들에서 일련의 과정을 반복한다. 분할정복으로 풀기 위해서는 다음 두 사항을 해결해야된다.어떻게 노드 v를 포함한 가장 좋은 경로를 찾을 수 있는가?수행시간을 최적으로 만들 노드 v를 어떻게 찾아야 하는가?우선 노드 v를 포함한 가장 좋은 경로를 찾는 법은 꽤 간단하다. 노드 v를 루트로 한 트리를 만들고 dfs를 돌리면 길이가 K이면서 가장 짧은 경로를 O(N)만에 찾을 수 있다. dfs를 돌릴 때 크기가 K인 배열을 이용해야한..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/garden.pdf 대회 때, 문제가 너무 어려워 보여 별다른 도전을 하지 못한 채 49점을 받았다. 최근에 문제를 다시 풀어보았을 때, 노가다 문제임을 알 수 있었고, 까다로운 코딩 끝에 만점을 받을 수 있었다. 대회 때 문제를 풀지 못한 것에 대한 아쉬움이 커졌다. 이 문제는 69점을 받는 방법이 딱히 생각 나지 않는다. 다만, 코딩할 때 배열 대신 vector를 썼을 때 시간초과로 69점을 받게 됬다. vector를 배열로 고치니 넉넉하게 만점이 나왔다. 대회 때 69점 받은 사람이 상당히 많은데, 69점을 받기 위한 쉬운 방법이 있는지 잘 모르겠다. 문제의 해법에 접근하게 위해서 몇 가지 관찰이 필요하다.어떤 노드 i에서..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/ricehub.pdf이 문제를 풀기 위해서, 어떤 구간이 있을 때, 그 구간에 있는 논들의 쌀을 다 가져오기 위한 최소 비용을 계산할 수 있어야한다. 구간 (i,j)가 있다는 것은 구간에 속한 논이 X[i], X[i+1], ..., X[j]라는 것이다. 이 때, 쌀창고는 X[(i+j)/2]에 놓는 것이 비용을 최소화 할 수 있다. 따라서, 구간 (i,j)에 대해 최소 비용을 O(N)의 전처리가 되어 있으면, O(1) 만에 구할 수 있다.이제 답은 최소 비용이 B를 넘지 않은 최대 구간 크기와 같다. 이를 O(N)만에 구할 수 있다. i=0, j=0에서 시작하여, i를 계속 증가 시켜가면서 구간 (j,i)의 최소 비용이 B를 넘으..

문제 ↓ 상당히 까다로워 보이는 문제다. 대회 당시 만점자가 많지 않지만 매우 어려운 문제에 속하진 않는다. 문제는 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$의 ..

공식 홈페이지: 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..

금년도 IOI에서 한국대표팀이 금메달 2개, 은메달 2개로 2009년 이후로 좋은 성적을 받았다. IOI2010부터 채점 환경이 갑작스레 바뀌게 되고 자연스럽게 출제할 수 있는 문제의 종류도 다양해졌다. 때문에 우리나라 선수들은 익숙치 못한 환경에 적응을 못하게 되었고 빛을 보기까지 3년정도가 걸린 셈이다.사실 문제 유형이 바뀌어 시험을 못보았다는 것은 핑계거리일 수 있다. 모두가 동일하게 변함을 맞이했고, 충분히 금메달을 받을 수 있는 교육을 받았기 때문이다. 특히, 미국팀이 성적이 엄청 좋았었는데, 그들이 많이 신기했었다. 그래도 코딩 정확성을 기준으로 연습했던 나에게는 큰 타격이었다.내가 2010년, 2011년 두 번 나갔을 때 모두 성적이 떨어지고 있을 때라... 이번 한국대표 선수들이 더 자랑스..