23575 Squid Game

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

물통 1, 2, 3에 각각 물이 $X, Y, Z$리터 들어있다. $x \le y$에 대해, $x$리터의 물이 들어있는 물통 $A$와 $y$리터의 물이 들어있는 물통 $B$을 선택하여, 물통 $A$에 $2x$리터, 물통 $B$에 $(y - x)$리터의 물이 남도록 물통 $B$에서 물통 $A$로 물을 붓는 동작을 할 수 있다. 처음 물의 양 $1 \le X \le Y \le Z \le 10^9$가 주어졌을 때, 1000번 이내의 동작으로 한 물통을 완전히 비우도록 하는 동작을 순서대로 출력하라. 물통 $B$에서 물통 $A$로 물을 붓는 동작을 $B: A$와 같은 꼴로, 각 동작마다 개행하여 출력하면 된다.

힌트

개인적으로는 상세한 풀이를 참고하지 않고 풀어볼 수 있다면 충분히 재미있는 문제가 될 것이라고 생각하여 이 문제에 대해 비슷한 감상을 갖는 이를 위해 문단을 추가하였습니다.

힌트 1: 제시될 풀이의 방향

동작을 통해 물통에 든 물의 최솟값을 줄일 방법에 대해 생각할 것이다.

힌트 2: 힌트 1의 상세

최대 30번 정도의 동작을 통해 최솟값을 2배 줄일 방법이 존재한다고 가정하면, $10^9 < 2^{30}$이므로, 대략 30번 정도의 이러한 동작 묶음을 통해 최솟값을 감소시켜 0으로 만들 수 있다.

힌트 3: 풀이 요약

물을 붓는 동작을 사용하여 나눗셈을 구현하였다. 최대 30번 정도의 동작을 통해 $x \le y$에 대해 $x, y$리터의 물이 담긴 물통으로부터 $y % x$리터 또는 $(k * x - y) % x$리터의 물이 남은 물통을 만들 수 있다 ($k$는 $k * x - y$를 음이 아닌 정수로 만드는 임의의 수이다). $x, y$에 따라 둘 중 하나를 선택하여 최솟값이 2배 줄일 수 있다. $10^9 < 2^{30}$이므로, 대략 30번 정도의 이러한 동작 묶음을 통해 최솟값을 감소시켜 0으로 만들 수 있다.

풀이

동작 묶음 구성

물통에 든 물의 양이 각각 $x, y, z$리터라고 하자. 물통 1, 2, 3에 각각 물이 $x, y, z$리터 들었을 때, $x \le y \le z$이도록 물통의 번호를 잘 바꾸자.

우선 $z$를 크게 만들고 나서 시작하려고 한다. $x + y < z$가 성립하지 않는다면 물통 3에서 물통 2로 물을 부을 것이다. 각 물통에는 $x, 2y, z - y$만큼의 물이 남는다. $y > 0$인 경우 $x + z < 3y$가 성립하는데, 아니라면 $x + z \ge 3y$이고 $x + y \ge z$이므로 $0 \ge 2y$이고 이는 모순이다. 이때 $x + (z - y) < 2y$이므로, 물통들의 번호를 적절히 바꾸고 새로운 값에 변수를 다시 붙여, 물통 1, 2, 3에 각각 물이 $x, y, z$리터 들었고, $x \le y \le z$와 $x + y < z$를 만족한다고 가정하자.

다음으로 물통에 남은 물의 양 중 최솟값이 $y \bmod x$리터 또는 $x - (y \bmod x)$리터 이하가 되도록 만들 것이다. $y = qx + r$, $0 \le r < x$라고 하자. $x \le y$이므로 $q \ge 1$이다. $q = 1$인 경우를 예시로 들어 어떤 전략을 취하여야 할지 생각하여 볼 것이다.

$x \le y < \frac{3}{2} x$인 경우, $y \bmod x$는 $\frac{1}{2}x$보다 작거나 같다. 이 경우에는 물통 2에서 물통 1로 물을 부었을 때 물통 2에 물이 $y \bmod x$리터 남는다.
$\frac{3}{2} x \le y < 2x$인 경우, $x - (y \bmod x)$는 $\frac{1}{2}x$보다 작거나 같다. 이 경우에는 물통 3에서 물통 1로 물을 부은 후, 물통 1에서 물통 2로 물을 부었을 때 물통 1에 물이 $2x - y = x - (y \bmod x)$리터 남는다.

각 경우는 $y \bmod x$와 $\frac{1}{2} x$를 비교하여 구별할 수 있다. $q > 1$인 경우에 비슷한 결과를 만들 수 있는지 탐색하자.

우선, $r = y \bmod x$가 $\frac{1}{2}x$보다 작거나 같다고 가정하자.

$q \bmod 2 = 0$일 때, 물통 3에서 물통 1으로 물을 부을 것이다. 물통 1, 2에 각각 물이 $2x, y$리터 남는데, $y = q/2 \cdot 2x + r$이다.
$q \bmod 2 = 1$일 때, 물통 2에서 물통 1으로 물을 부을 것이다. 물통 1, 2에 각각 물이 $2x, y - x$리터 남는데, $y - x = (q - 1)/2 \cdot 2x + r$이다.

위 과정 이후 $q$에 $q/2$를 대입하고, $q > 1$인 동안 위 과정을 반복한다. 물통 3에 물이 충분히 있으므로 위 과정은 잘 동작한다. $q = 1$이 되었을 때 전술한 동작을 통해 물통 2에 물을 $r$리터 남길 수 있다.

$r$이 $\frac{1}{2}x$보다 크거나 같다고 가정하자. 새로운 과정을 소개하기 전에, 위 과정을 분석하여 보자. 위 과정은 물통 2에 $r = y - qx$리터를 남기게 된다. 이 과정은 직관적으로는 다음과 같이 이해할 수 있다:

두 물통의 물 차이가 $y - qx$리터가 될 때까지 물을 잘 옮긴다.
마지막 동작을 통해 차이를 실현한다.

그러니 이번에는 다음과 같이 과정을 설계할 수 있을 것이다:

두 물통의 물 차이가 $(q + 1) x - y$리터가 될 때까지 물을 잘 옮긴다.
마지막 동작을 통해 차이를 실현한다.

따라서 $q$ 대신 $q + 1$를 초기값으로 주어 위 과정을 반복하고, 마지막 동작에서 물통 1에서 물통 2로 물을 부어 물통 1에 $(q + 1) x - y = x - r$리터를 남길 수 있다.

위 동작 묶음을 수행하였을 때, 남아있는 물의 양 중 최솟값이 기존 최솟값의 $\frac{1}{2}$보다 작거나 같게 된다. 최솟값을 줄이는 위의 과정을 동작 묶음이라고 부르자. 동작 묶음이 수행될 때마다 물의 양의 최솟값이 줄어들게 되므로, 동작 묶음을 유한하게 많이 사용하여 물통 하나를 비울 수 있다. 따라서 위 동작 묶음에 따라 동작을 나열하는 해답의 정당성이 증명된다.

분석: 동작 횟수

그러나 이 문제는 단지 동작을 나열할 뿐이 아니라, 동작의 횟수가 1000회로 제한되어 있다. 따라서 위 풀이를 검증하기 위해서는 동작의 정당성 뿐만 아니라 횟수에 대해서도 추가적인 분석이 필요하다.

풀이에 서술된 동작 묶음에 동작이 최대 몇 개 포함되었는지 분석하여 보자.

$x + y < z$를 가정하기 위해 최대 1회
$q = \left\lfloor \frac{y}{x} \right\rfloor \le 10^9 < 2^{30}$. $1 + \lfloor \log_2 q \rfloor \le 30$회.

따라서 각 동작 묶음 당 최대 31회의 동작을 수행한다. 초기 최솟값은 $10^9 < 2^{30}$이므로, 최솟값을 절반씩 줄이는 경우 동작 묶음을 최대 31회 사용한다. 따라서 위 풀이는 동작을 최대 $31 \cdot 31 < 1000$회 사용한다. 이는 문제의 조건과 일치한다.

대부분의 경우 1000회보다 훨씬 적은 횟수로 해답이 나올 것 같지만 적당한 분석을 수행할 수 없었다.

계산 복잡도

시간이 아주 오래 걸리지는 않는다. 각 수행마다 $x + y < z$, $q \bmod 2$ 정도만 살피면 되기 때문이다. 시간 0ms으로 동작하는 해 또한 구성할 수 있다.

문제의 조건이 $1 \le X \le Y \le Z \le N$으로 주어졌을 때, 위 분석을 사용하면 답의 크기는 $\mathcal{O}((\log N)^2)$ 정도일 것으로 추측한다.