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$의 ..

공식 홈페이지: 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년 두 번 나갔을 때 모두 성적이 떨어지고 있을 때라... 이번 한국대표 선수들이 더 자랑스..

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/game/game - KOR (ko).pdf 영문: http://www.ioi2013.org/wp-content/uploads/tasks/day2/game/game.pdf이 문제는 전형적인 2차원 Segment Tree 문제다.흔히들 알고 있는 Indexed tree로 이 문제를 풀 경우 $R$ 값이 매우 커 배열을 잡을 수 없지만, top-down 방식을 이용하는 segment tree를 이용하면 된다. 이 문제는 online 방식으로 이후 데이터가 어떻게 들어올지 전혀 예측하지 못한 채로 함수를 코딩해야 되기 때문에 re-indexing 혹은 re-numbering 을 할 수 없다. 불가피하게 seg..

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/robots/robots - KOR (ko).pdf이분검색으로 미리 답을 정해놓은 뒤 그리디를 통해 답이 되는지 확인하는 방법을 사용한다. 이런 테크닉은 파라매트릭 서치(Parametric Search)로 알려져 있다.만약 로봇의 종류가 한 가지라면 매우 쉽게 풀릴 것이다. 하지만, 로봇의 종류가 2 종류 (연약한 로봇, 작은 로봇)이라 생각하기 많이 까다로울 수 있다.답을 $m$ 이라 가정했다는 것은 각 로봇은 최대 $m$ 개의 장난감을 운반할 수 있다는 것이다. 먼저 연약한 로봇들이 연약한 순서대로 자신이 가져갈 수 있는 가장 '크기'가 큰 장난감들을 $m$개 운반한다. 만약 가져갈 수 있는 장난감이..

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/cave/cave - KOR (ko).pdf0번 문 부터 차례대로 매치되는 스위치를 찾아가는 방식으로 한다. 0번 문과 매치되는 스위치를 찾기 위해서 이분검색을 한다. 스위치 후보들이 $N$개 있을 때 그 중 반절만 뒤집는다. 이 때 0번 문이 움직이는지 확인하면서 후보들의 개수를 반으로 줄일 수 있다. 이렇게 후보가 하나 남을 때 까지 진행한다. 마지막 남은 후보가 0번 문과 매치되는 스위치다.0번 문과 매치되는 스위치를 찾고 그 스위치의 답을 찾는건 1번의 시도만으로 가능하다. 0번 문과 매치되는 스위치의 답을 찾은 이후 부터는 0번 문은 항상 열려있는 상태를 유지한다. 그러면 1번 문의 스위치를 찾..