PS 이야기

문제: 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번 경우 해결을 ..