이라 두자. 에 대해 라 정의하고, 편의상 이라 둔다. 좌표가 모두 다르므로 이고, 이면 이다.
번 개구리가 도달할 수 있는 좌표의 집합을 라 하면 다음과 같다. 이다. 이면 이다. 이면 는 또는 인 모든 정수 의 집합이다. 더 나아가, 서로 다른 좌표 를 하나씩 고른 모든 배치는 실제로 만들 수 있다.
도달 가능 집합의 증명
모든 좌표에서 를 빼서 번 개구리를 에 놓자. 보다 번호가 큰 개구리들의 좌표의 최대공약수는 처음에 이고 항상 유지된다. 실제로 한 좌표를 에서 로 바꾸어도 이다. 따라서 모든 점프의 중심은 의 배수이고, 번 개구리의 좌표는 를 법으로 부호만 바뀔 수 있다. 이는 위 조건의 필요성을 보인다.
도달 가능 집합들은 강한 포함 관계를 가진다. 이면 이거나 이다.
층상 구조의 증명
이면 이고, 도 의 배수이다. 두 집합이 한 좌표에서 만난다고 하자. 의 두 나머지 와 를 로 줄이면 의 두 나머지 와 가 된다. 또한 이므로 의 모든 좌표가 에 속한다. 인 유한 집합과 도 같은 논리로 처리된다.
이제 순서로 개구리를 처리한다. 각 개구리를 자신의 도달 가능 집합에서 이미 사용된 좌표를 제외하고 가 가장 작은 좌표에 놓는 그리디가 최적이다.
그리디의 최적성 증명
번호가 큰 개구리들에 대해 그리디와 같은 좌표를 사용하는 최적 배치를 하나 잡자. 현재 번 개구리에 대해 그리디가 고른 좌표를 , 최적 배치가 고른 좌표를 라 하자. 도 번호가 큰 개구리들이 사용하지 않은 후보이므로 이다.
남은 것은 각 에서 절댓값이 가장 작은 빈 좌표를 찾는 일이다. 일 때 라 하자. 나머지 을 으로 정규화하면 그 나머지류의 좌표는 양의 방향의 와 음의 방향의 이다. 단, 인 경우 음의 방향은 에서 시작한다.
역을 보이자. 번호가 큰 개구리들을 유한 집합 에 고정하고 한 개구리만 움직인다고 하자. 이고 라 하자. 를 중심으로 한 반사를 라 쓰면 은 만큼의 평행이동이다. 베주 항등식으로 만큼의 평행이동을 만들 수 있고, 으로 부호를 바꿀 수 있으므로 장애물을 무시한 궤도는 정확히 앞에서 구한 나머지류들이다.
착지점은 비어 있어야 하므로 를 피할 수 있음도 확인해야 한다. 궤도가 와 만나지 않으면 자명하다. 만나면 그 궤도는 하나의 등차수열이 된다. , 라 하자. 밖의 어떤 궤도 점도 를 이용해 보다 오른쪽으로 옮길 수 있고, 두 반사를 번갈아 적용하면 임의로 멀리 보낼 수 있다. 만큼 이동시키는 고정된 유한 반사열을 충분히 멀리서 적용하면 모든 중간 좌표가 밖에 있다. 따라서 같은 궤도의 임의의 두 빈 좌표 사이를 이동할 수 있다.
마지막으로 개구리 수에 대해 귀납한다. 번 개구리를 목표로 옮기는 유한한 과정에서 등장하는 좌표는 유한 개뿐이다. 이면 은 무한하므로, 그 좌표들을 모두 피하는 곳에 번 개구리를 주차할 수 있다. 나머지 개구리를 옮긴 뒤 번 개구리를 목표로 옮긴다. 는 직접 확인할 수 있다. 이로써 서로 다른 대표 좌표를 고른 모든 배치가 실제로 도달 가능하다.
가 최적 배치에서 비어 있다면 번 개구리를 로 옮겨도 최댓값은 증가하지 않는다. 아니면 어떤 번 개구리가 를 사용한다. 이고 이므로 층상 구조에 의해 이다. 따라서 이고, 번과 번 개구리의 좌표 를 맞바꿀 수 있다. 사용되는 좌표의 집합과 최댓값은 그대로이다. 이 교환을 반복하면 어떤 최적 배치가 그리디 전체와 일치한다.
현재 법 의 각 나머지마다 두 방향에서 아직 확인하지 않은 첫 좌표를 저장한다. 전체 사용 좌표는 해시 집합에 저장하고, 포인터가 사용된 좌표를 가리키는 동안 한 칸씩 진행한다. 를 이루는 두 나머지에서 얻은 최대 네 후보 중 가장 좋은 것을 고르면 된다. 이면 와 만 비교한다.
를 감소시키며 를 갱신한다. 법이 바뀌면 나머지별 포인터만 초기화하고 사용 좌표 집합은 유지한다. 양수인 가 바뀔 때마다 이전 값의 진약수가 되므로 절반 이하로 감소한다. 따라서 서로 다른 법은 개뿐이다. 하나의 법이 유지되는 동안 각 사용 좌표는 포인터에 의해 최대 한 번 건너뛰어지므로 전체 기대 시간 복잡도는 , 메모리 복잡도는 이다.
Solution written by GPT5.6
