[문제 설명]
0부터 D까지 거리 사이에 N개의 돌이 있을 때, 개구리가 돌을 적절히 밟아 최소화된 the maximum distance of a single leap을 구하는 문제.
[해결 방법]
left bank, big stones, right bank를 무조건 밟는다고 생각하고 이들을 check point라고 하겠다. 인접한 두 check point 와 그 사이의 small stones들의 left bank로부터 떨어진 거리들을 자료구조에 집어 넣고 인덱스가 2 차이가 나는 거리들의 차이의 최댓값을 저장했다. 모든 인접한 check point들에 대해 이런 최댓값들을 저장한 후에 그 최댓값을 출력하였다.
[Correctness]
풀이를 나눠서 생각해보겠다. 우선 big stones들을 무조건 밟게 하였다. 임의의 stone의 x좌표가 M, left bank에서 right bank까지 도약하는 거리가 D였으므로 임의의 stone을 밟고 도약하는 거리는 M과 D - M이 된다. 여기서, M은 $0 < M < D$였으므로 항상 $M < D$와 $D - M < D$를 만족한다. 즉 모든 stones를 밟고 가는 것이 최적해가 되고, big stones는 밟는 횟수에 제한이 없으므로 항상 밟아야 한다.
이제 이 문제는 인접한 두 check point 사이의 small stones를 적절히 밟아서 최적해를 만드는 문제가 되었다. 하나의 small stone이 갖는 경우의 수는 이동할 때 밟는 경우, 돌아올 때 밟는 경우, 밟지 않는 경우로 세 가지이다. 그런데 위에서 모든 stones를 밟고 가는 것이 최적해가 됨을 증명하였다. 즉 stones는 갈 때 밟은 stones의 집합과 돌아올 때 밟은 stones의 집합이 된다.
그렇다면 두 check point와 양쪽 집합의 인접한 stones끼리의 거리가 오고 갈 때의 도약 거리가 되고, stones를 양쪽의 집합에 적절히 배치하여 두 check point와 양쪽 집합의 인접한 stone끼리의 거리를 최소로 만든다면 그 거리 중의 최댓값이 최소화된 the maximum distance of a single leap이 된다.
그렇다면 check point와 양쪽 집합의 인접한 stones의 거리를 최소로 하는 문제만 남게 되었다. 이를 해결하기 위해 left bank에 가까운 check point를 $s_1$, right bank에 가까운 check point를 $s_k$, 그 사이에 존재하는 small stones가 $k - 2$개라고 하면 small stones를 $s_2, s_3, ... s_{k-1}$ 이라고 하여 전체적으로 $s_1, s_2, ... , s_k (k > 3)$라고 하겠다. 그리고 $s_i$가 left bank로부터 떨어진 거리를 $M_i$라고 하겠다. $k = 3$인 경우에 $s_3 - s_1$이 the maximum distance of a single leap임은 당연하므로 $k > 3$인 범위에 대해서만 증명하겠다. 인접한 두 개의 원소 $s_i, s_{i + 1} (1 < i < k - 1,$ 범위는 이하 생략)가 하나의 집합에 들어간다면 반대 집합의 최소 거리는 $M_{i + 2} - M_{i - 1}$가 된다. 하지만 $M_{i + 2} - M_{i - 1}$은 항상 $M_{i + 1} - M_{i - 1}$과 $M_{i + 2}, M_{i}$보다 크다.
그러므로 인접한 두 개의 원소 $s_i, s_{i + 1} (1 < i < k - 1)$를 서로 다른 집합에 배치시키는 것이 최적해이고, 위 해결 방법은 correct하다.
[Time Complexity]
check point로 나누어 stones를 따로 처리했지만 결국 하나의 돌에 대해 최소 한 번, 최대 두 번 검사했다. 그러므로 총 시간복잡도는 TestCase가 T개, 돌이 N개로 O(TN)이다.
[소스 코드] / C++
분실함