[IOI2013 Day2] Robots 해법

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/robots/robots - KOR (ko).pdf

이분검색으로 미리 답을 정해놓은 뒤 그리디를  통해 답이 되는지 확인하는 방법을 사용한다. 이런 테크닉은 파라매트릭 서치(Parametric Search)로 알려져 있다.

만약 로봇의 종류가 한 가지라면 매우 쉽게 풀릴 것이다. 하지만, 로봇의 종류가 2 종류 (연약한 로봇, 작은 로봇)이라 생각하기 많이 까다로울 수 있다.

답을 $m$ 이라 가정했다는 것은 각 로봇은 최대 $m$ 개의 장난감을 운반할 수 있다는 것이다. 먼저 연약한 로봇들이 연약한 순서대로 자신이 가져갈 수 있는 가장 '크기'가 큰 장난감들을 $m$개 운반한다. 만약 가져갈 수 있는 장난감이 $m$개 보다 적다면 그것들을 모두 운반한다.

그리고나서 남은 장난감들을 작은 로봇들이 작은 순서대로 자신이 가져갈 수 있는 장난감을 $m$개 운반한다. 아까와 마찬가지로 가져갈 수 있는 장난감이 $m$개 보다 적다면 그것들을 모두 운반한다.

최종적으로 장난감이 남아있지 않으면, 즉, 로봇들이 장난감들을 모두 운반했으면 $m$은 답이 될 수 있다. 그렇지 않은 경우 답은 $m$보다 크다.

처음에 이와 같은 방법으로 연약한 로봇들이 장난감을 가져갔으면 최대한 많은 장난감을 운반함과 동시에 남은 장난감들의 크기들은 최소이기 때문에 방법이 유효하다.

코드: http://ideone.com/Qv54os