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

해법: http://ace.delos.com/TESTDATA/FEB11.lostcows.htm 이 문제에서 현재 소가 k개의 목장에 위치해있다고 하자. FJ의 다음 sign 명령에 의해 이동 한 뒤에는 k개 이하의 목장에 위치해있다. * 예제 데이터에서 소가 처음에 1,2,3,4목장 (4개 목장)에 위치해있고 Sign 1의 명령을 받으면 소가 1,3,4목장 (3개 목장)에 위치하게 된다. 이는 쉽게 증명 가능하다. 그러면 우리는 항상 특정한 sign 명령 순열을 통해 목장 a에 있고, 목장 b에 있는 소를 목장 1(최종 도착지)에 모이게 할 수 있다. (답은 항상 존재한다고 했으므로) 이 특정한 sign 명령 순열은 bfs를 통해 계산할 수 있다. 방법은 소스 참고.

문제: http://z-trening.com/tasks.php?show_task=5000000691 해법: http://ace.delos.com/TESTDATA/NOV08.toy.htm * 이 문제 20번 데이터 출력 파일이 잘못 되었습니다. 올바른 답은 106110559이 아닌, 105265954 입니다. 해법 페이지에 있는 소스코드로 20번 입력데이터를 돌려보면 알 수 있습니다. 우선, N1 > N2, C1 < C2로 가정하자. 만약 아니라면 소독 회사가 하나만 있다고 볼 수 있기 때문이다. 미리 장난감을 총 t개 산다고 정하자. 그러면 이제 장난감을 총 t개 산다고 할 때, 소독하는데 최소 비용을 구해야한다. 문제에서는 장난감을 사용한 뒤, 장난감을 소독 회사에 맡긴다고 되어있는데, 우리는 미래의 ..

문제: http://www.ii.uni.wroc.pl/boi/index.phtml?id=11 테스트데이타: http://www.ii.uni.wroc.pl/boi/task/tel.zip Task 발틱 해에는 두 개의 섬이 있다. Bornholm과 Gotland. 우리는 이 두섬 사이에 순간이동 장치를 놓을 생각이다. 순간이동 장치에는 Sending과 Receiving, 두가지 모드가 있다. Receiving --- 다른 순간이동 장치가 이 순간이동 장치로 들어올 수 있다. Sending --- 이 순간이동 장치에 들어가면 다른 섬의 특정한 순간이동 장치로 이동된다. (당연히 그 특정한 순간이동 장치는 Receiving 모드여야한다.) 당신은 처음 순간이동 장치들의 모드를 정하고 바꾸지 못한다. 그런데 쓸모..

문제: http://www.csc.kth.se/contest/boi/monument.pdf 해법: http://www.csc.kth.se/contest/boi/monument-spoiler.pdf 재미있는 문제다.. BOI 문제들 다 재미있는 듯... 만만한 문제 하나 없다.. O(N^5) 부터 O(N^3) 까지 다양한 방법이 있지만, O(N^3) 만에 해결해야한다 ^^... 그 방법을 소개하겠다. Dynamic Programming 을 통해 각 점 (x,y,z)마다 xy 평면에서 점 (x,y,z)를 오른쪽-가장자리로 하는 정사각형의 최대 크기를 precompute(선처리) 해놓을 수 있다. 그 값을 D[x][y][z]라 하자. 그러면 이제 (x,y)의 z축에서 값들을 관찰할거다. (x,y)를 정하고 한..

문제: http://www.csc.kth.se/contest/boi/subway.pdf 해법: http://www.csc.kth.se/contest/boi/subway-spoiler.pdf 이 문제에 대한 증명을 하지는 못 하겠다... 그냥 느낌으로 올 뿐이지 증명이 가능한지는... 잘 모르겠다... ㅠㅠ 예제 2번 데이터를 통하여, 방법을 설명하겠다. 1. 우선 처음에 입력 받을 때 방향에 상관없이 입력받고, 오름차순 정렬을 한다. 9 15 33 33 41 81 97 100 2. 홀수번째와 짝수번째의 방향을 다르게 한다. 9R 15L 33R 33L 41R 81L 97R 100L 3. 다음에 subway의 rail을 일직선에 나타내고 그에 따라 x좌표를 대입한뒤 정렬하면, 9 (200-15) 33 (20..