PS 이야기

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

금년도 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번 문의 스위치를 찾..

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day1/wombats/Wombats ko (KOR).pdf 상당히 까다로운 문제다. 이 문제의 해법은 $C$ 값이 $R$ 값에 비해 상대적으로 작다는 사실에서부터 시작한다. 행 X와 행 Y가 있을 때 행 X의 어느 점에서 행 Y의 어느 점으로 가는 $C^2$가지 경우에 대해 사전계산(precompute) 할 수 있다. {X,Y} 를 사전계산 해놓은 것이라 하자. {X,Y}와 {Y,Z}를 합쳐 {X,Z}를 만들 수 있다. 간단하게 합치는 시간복잡도는 $O(C^3)$이지만, Knith-Optimization과 비슷한 방법으로 $O(C^2)$ 시간복잡도를 갖으며 합칠 수 있다. 이를 위해서는 한 가지 중요한 아이디어..

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day1/dreaming/Dreaming ko (KOR).pdf $N-M-1$개의 간선을 새로 추가하고 나서 답이 될 수 있는 경우는 다음과 같다. 기존의 트리에 있는 최장 경로새로운 간선이 포함되는 최장 경로1번 경우를 계산하기 위해, 우리는 트리 내의 최장 경로의 길이를 구해야한다. 트리 내에 최장 경로를 트리의 '지름'이라고 말한다. 트리의 지름 구하는 방법은 여러가지가 존재하는데, 그 중 하나는 어떤 한 정점을 잡고, 그 점과 가장 먼 점 $v$를 찾고, 다시 $v$ 에서 제일 먼 경로를 찾으면 그 경로가 트리의 지름이 된다. 처음에 기존에 있는 트리들의 지름을 구하고 답으로 갱신한다. 2번 경우 해결을 ..