B번 증명에 어긋나는 경우가 있습니다.

위와 같이 경로가 선택되었을 경우

- 파란색 쿠키 경로 확정
- 빨간색 쿠키 경로 확정
- 회색 쿠키는 즉시 출발하면 파란색 쿠키와 1초 뒤에 충돌하므로, 1초 기다렸다 출발함
- 회색 쿠키가 1초 뒤에 출발하면 빨간색 쿠키와 1초 뒤에 충돌하므로, 1초 더 기다렸다 출발함
- 회색 쿠키가 2초 이상 기다렸다가 출발하면 파란색 쿠키는 항상 회색 쿠키와 충돌하므로 자신의 경로를 따라갈 수 없음

즉 두 쿠키가 같은 구간을 서로 반대 방향으로 이동한다면 나중에 출발하는 쿠키는 (a, b)와 (c, d)가 역순으로 등장하므로 문제가 생깁니다.

만약 두 쿠키가 서로 반대 방향으로 이동하는 구간이 있다면 그 구간을 삭제하고 두 쿠키에 할당된 구멍을 서로 바꿔 주는 과정을 반복하면 이런 구간이 없도록 답을 변형할 수 있습니다.

오랜만에 다시 증명을 보니 예외 케이스가 생각보다 더 많네요. Thanks to @cubelover

이 경우는 세 쿠키의 이동 경로의 길이가 전부 같지만, C1 - C2 - C3 순으로 결정할 경우 다음과 같은 오류에 빠집니다.

- C1이 0초에 출발
- C2가 0초에 출발
- C3은 0초에 출발하면 C2와 충돌, 1초에 출발하면 C1과 충돌하므로 2초 이상 기다린 뒤 출발해야 함
- 그런데 C3이 2초 이상 기다리면 C1이 자신의 경로대로 이동할 수 없음

따라서 이 경우 C3은 반드시 C1보다 먼저 결정되어야 합니다. 일반화해서, 어떤 쿠키 A의 이동 경로 위에 B의 출발점이 놓여 있다면 B의 출발 시각은 A의 출발 시각보다 먼저 결정되어야 합니다.

하지만 여러 쿠키들의 경로가 cycle을 이룰 경우 순서를 결정지을 수 없습니다.

이 경우 cycle을 제거하고, 만약 그 결과로 나온 경로가 최단경로가 아닐 경우 최단경로로 바꿔 주는 작업을 반복해서 cycle이 없고 모든 쿠키-구멍 쌍이 최단경로인 배치를 만들 수 있습니다.
cycle을 제거하는 작업과 최단경로로 만드는 작업 모두 경로의 길이의 총합이 감소하기 때문에 언젠가는 수렴합니다.

결론적으로,

- 각 쿠키가 할당된 구멍까지 다른 구멍을 밟지 않고 이동하는 배치를 만든다.
- 해당 배치가 cycle이 없고 모든 쿠키가 최단경로로 이동하도록 배치를 수정한다.
- A의 이동 경로 위에 B의 출발점이 있을 경우 B가 A보다 우선이 되도록 쿠키들을 위상정렬한 뒤 출발 시각을 결정한다.

와 같은 사전 작업을 거치고 풀이에 있는 증명을 따라가면 비로소 상한이 HW - 1임을 증명할 수 있습니다.

위의 증명의 경우 A의 이동 경로 위에 B의 출발점이 있을 경우, A가 B의 시작 위치에 도달하기 전에 B가 출발해야 한다는 조건으로 인해 전처리 과정을 거쳐도 증명이 성립하지 않는 것을 발견했습니다. 다른 방향으로 접근한, 더 약한 결론을 얻는 증명을 새로 생각해봤습니다.

-

쿠키가 모두 탈출하는데 최악의 경우 얼마나 시간이 걸리는지 살펴보자. 1<=i<=n 에 대해 쿠키  Ci가 구멍  Hi로 탈출하는 것이 답이라고 하자. 그럼  Ci가 Hi까지 최단 경로를 따라 움직이는 답안을 생각할 수 있다. 추가적으로 여기서 서로 다른 쿠키의 경로가 사이클을 이룬다면 사이클을 제거하는 것이 항상 이득이므로 그렇게 전처리를 하자.

그럼 각 시각별 쿠키의 상태를 트리 형태로 나타낼 수 있다. 트리의 각 노드는 쿠키가 있는 칸 또는 쿠키가 가고자 하는 칸을 나타낸다. 어떤 칸 X에 있는 쿠키가 다른 칸 Y(그곳에 쿠키가 있든 없든)로 가려고 하는 경우 트리에선 Y가 X의 부모가 되게 설정한다. 이 경우 각각 트리의 루트는 항상 쿠키가 없는 칸을 나타내고, 그 외의 노드는 모두 쿠키가 있는 칸을 나타내게 된다.

전처리를 했기 때문에 서로 다른 쿠키의 경로는 사이클을 이루지 않으므로 임의의 시각에서 격자의 상태를 트리 형태로 나타낼 수 있다. 또한 격자에서 인접한 칸끼리만 트리에서 간선이 존재할 수 있고, 상하좌우 4칸에서 중앙칸으로 가려고 하는 경우는 없기 때문에 트리의 branching factor는 최대 3이다.

이제 각 시각별로 최소 몇 개의 쿠키가 자기 경로의 다음 칸으로 나아갈 수 있는지 알 수 있다. 한 트리에서 루트부터 리프까지 가는 경로를 잡았을 때, 경로에 있지 않은 쿠키는 모두 제자리에 있고 경로에 있는 쿠키는 모두 다음 칸으로 가게 할 수 있다. 따라서 각각 트리의 최대 깊이의 합만큼의 쿠키가 다음 시각에 움직일 수 있다. 이 값은 모든 쿠키가 한 트리에 속하고(즉 모든 쿠키끼리 충돌하는 관계가 성립하고), 균형잡힌 트리일 때 가장 작게 된다. 즉 아직 구멍에 빠지지 않은 쿠키의 수가 n일 때 최소  log_3(n)개의 쿠키가 다음 칸으로 갈 수 있다.

그럼 처음 상태에서부터 마지막 쿠키가 탈출할 때까지 걸리는 시간은 최대 얼마일까? 각 쿠키  Ci가 매칭된 구멍  Hi까지 가는 경로의 길이는 최대  HW-n이고, 각 시각별로 쿠키가 움직일 때 남은 경로의 길이가 가장 짧은 쿠키가 먼저 움직이는 것이 최악의 경우인데, HW 가 100일 때 이 조건대로 시뮬레이션( https://gist.github.com/wwiiii... )을 하면 쿠키가 몇 개든 1000초 이내에 모두 탈출할 수 있음을 알 수 있다. 이진 탐색의 위쪽 경계를 1000초로 둘 경우 아슬아슬하게 1초에 실행이 끝나는데, 실제 상황에선 이런 경우가 있을 수 없으므로 그보다 좀 더 작은 값을 위쪽 경계로 두고 코딩하면 시간 내에 안정적으로 동작한다.

-