Mecho (IOI 2009)

https://www.acmicpc.net/problem/5465

격자상에 어떠한 점도 Mecho가 일찍 도착하는 것이 무조건 이득이라는 점을 쉽게 관찰할 수 있다.

이는 Mecho가 t만큼 꿀을 빨고 출발했을 때 도착할 수 있다면, t보다 작거나 같은 시간 u만큼 꿀을 빨고 출발해도 항상 도착할 수 있다는 것을 의미한다.

때문에 t의 정의역을 설정해 준 후 Parametric Search를 해주면 문제를 쉽게 풀 수 있다.

이제 과제는 시간 t만큼 꿀을 빤 이후에 Mecho가 집에 도착할 수 있는지에 대한 문제로 귀결된다.

먼저, 벌들의 위치를 한꺼번에 Queue에 넣은 다음에 너비 우선 탐색을 할 경우, 한 격자에 도달하기까지 벌이 걸리는 시간을 쉽게 O(n^2) 에 precompute할 수 있다.

벌이 도달하는 시간이 알려져 있을 때는, (곰이 방문하는 시간) < (벌이 도달하는 시간) 을 만족할 때 방문할 수 있음을 알 수 있으며, 곰이 방문하는 시간은 t + (현재 거리) / s 라는 수식으로 표현할 수 있다.

위에서 말한 제약 조건을 BFS에 추가한 후 너비 우선 탐색을 진행하고, 도착점에 도달할 수 있다면 Mecho는 t 시간에 꿀을 빨 수 있다. t의 정의역을 0 ~ 시작점에 벌이 도달하는 데 걸리는 시간 - 1로 잡은 후 Parametric Search를 하면 문제를 해결할 수 있다.

벌이 도달하는 시간의 bound는 많아야 N^2이니, 문제는 O(N^2lgN) 에 해결 가능하다.