Frogs

$B=X_N$이라 두자. $i<N$에 대해 $G_i=\gcd(|X_{i+1}-B|,\ldots,|X_N-B|)$라 정의하고, 편의상 $G_N=0$이라 둔다. 좌표가 모두 다르므로 $G_{N-1}=0$이고, $i\le N-2$이면 $G_i>0$이다.

$i$번 개구리가 도달할 수 있는 좌표의 집합을 $S_i$라 하면 다음과 같다. $S_N=\{B\}$이다. 이면 이다. 이면 는 또는 인 모든 정수 의 집합이다. 더 나아가, 서로 다른 좌표 를 하나씩 고른 모든 배치는 실제로 만들 수 있다.

도달 가능 집합의 증명

모든 좌표에서 $B$를 빼서 $N$번 개구리를 $0$에 놓자. $i$보다 번호가 큰 개구리들의 좌표의 최대공약수는 처음에 $G_i$이고 항상 유지된다. 실제로 한 좌표를 에서 로 바꾸어도 이다. 따라서 모든 점프의 중심은 의 배수이고, 번 개구리의 좌표는 를 법으로 부호만 바뀔 수 있다. 이는 위 조건의 필요성을 보인다.

도달 가능 집합들은 강한 포함 관계를 가진다. $i<j$이면 $S_i\cap S_j=\varnothing$이거나 이다.

층상 구조의 증명

$i<j$이면 $G_i\mid G_j$이고, 도 의 배수이다. 두 집합이 한 좌표에서 만난다고 하자. 의 두 나머지 와 를 로 줄이면 의 두 나머지 와 가 된다. 또한 이므로 의 모든 좌표가 에 속한다. 인 유한 집합과 도 같은 논리로 처리된다.

이제 $N,N-1,\ldots,1$ 순서로 개구리를 처리한다. 각 개구리를 자신의 도달 가능 집합에서 이미 사용된 좌표를 제외하고 $|x|$가 가장 작은 좌표에 놓는 그리디가 최적이다.

그리디의 최적성 증명

번호가 큰 개구리들에 대해 그리디와 같은 좌표를 사용하는 최적 배치를 하나 잡자. 현재 $i$번 개구리에 대해 그리디가 고른 좌표를 $x$, 최적 배치가 고른 좌표를 $y$라 하자. $y$도 번호가 큰 개구리들이 사용하지 않은 후보이므로 $|x|\le|y|$이다.

남은 것은 각 $S_i$에서 절댓값이 가장 작은 빈 좌표를 찾는 일이다. $G_i>0$일 때 $m=2G_i$라 하자. 나머지 을 으로 정규화하면 그 나머지류의 좌표는 양의 방향의 와 음의 방향의 이다. 단, 인 경우 음의 방향은 에서 시작한다.