길이가 $N$이고 정확히 $M$개의 1을 포함하는 binary string에서 시작하여, 001 → 110과 100 → 011의 조작만을 사용하여 0을 1개만 남기고 모두 1로 만들려고 한다. 시작 시에 두 1이 이웃하면 안된다. 이것이 가능한지 판별하고, 가능하다면 그러한 binary string을 아무거나 하나 찾아서 출력하시오.

  • $5 \le N \le 10^6$, $1 \le M \le \lceil \frac{N}{2} \rceil - 1$

아이디어

몇 가지 입력에 대해 손으로 이것저것 시도해 보다가 아래의 패턴을 발견하였다.

먼저, 최종 상태에서 거꾸로 가는 것을 생각해보자. 1로만 이루어진 string에서 하나를 0으로 바꾸고, 110 → 001과 011 → 100을 써서 더 이상 조작이 불가능해질 때까지 조작하면 된다.

0이 하나인 string에서 1회 조작하면 반드시 두 개의 0이 이웃한 string이 되므로, 시작점을 이 상태로 바꿔서 생각한다. 또한, 두 개의 0을 기준으로 왼쪽의 1들과 오른쪽의 1들에 대해서 꽤 한정적인 조작만 가능함을 알 수 있다.

$N$이 짝수일 경우

양쪽 1의 길이가 모두 짝수이면, 다음과 같이 “모아서 밀기” 동작이 가능하다.

11111100111111
 ->        <-
00101011010100
    <-
01000000010100

왼쪽의 1의 개수가 $2a$개, 오른쪽의 1의 개수가 $2b$개이면, 최종적으로 왼쪽에 1개, 오른쪽에 $b-1$개의 1이 남게 된다. 1의 총 개수는 $b$개이다. 이러한 모아서 밀기 동작은 $a \ge 1$, $b \ge 1$일 때 성립하므로, $N$이 짝수이고 $1 \le M < \frac{N}{2} - 1$인 경우 이 방법으로 풀 수 있다. $M = \frac{N}{2} - 1$인 경우는 $a = 0$이라고 생각하고 전부 왼쪽으로 밀면 답을 얻을 수 있다. (최종적으로 1의 위치의 패턴이 같기 때문에 이렇게 구현하면 edge case 처리를 하나 줄일 수 있다.)

$N$이 홀수일 경우

반면, $N$이 홀수이면 한쪽 1의 길이가 홀수가 되며, 그 쪽의 맨 끝의 1은 어떻게 해도 지울 수 없을 것이라고 추측할 수 있다. 0쪽으로 모을 때 맨 끝의 1과 다음 1 사이에 0이 두 개가 남고, 그 1쪽으로 다시 밀어도 사이에 0이 하나 남기 때문이다.

조금 더 엄밀한 증명은 invariant를 찾아보면 된다. 이 부분은 tlsdydaud1님의 기여를 참고하였다.

두 개의 연속한 0이 있는 초기 상태에서 맨 왼쪽 0과 맨 오른쪽 0의 인덱스의 차이는 1, 즉 홀수이다. 여기서 조작을 몇 번 하더라도 맨 왼쪽에 있는 0의 오른쪽에 두 개의 1이 오도록 할 수 없음을 증명할 수 있다. 각 칸에 피보나치 수열로 가중치를 주고 0의 위치의 가중치의 합을 관찰하면 된다.

0  1  1 1 1 1 1
21 13 8 5 3 2 1

이렇게 가중치를 주면 어떻게 변환을 하더라도 가중치가 항상 같거나 증가한다. 그러나 최종적으로 맨 왼쪽에 2개의 1을 놓으려면 가능한 최대 가중치는 $8 + 5 + 3 + 2 + 1 = 19$밖에 안되므로 불가능하다. 피보나치의 $n$번째 항까지의 합은 항상 피보나치 $n+2$번째 항보다 작으므로 이것은 일반적으로 성립한다.

따라서, 맨 왼쪽의 0은 왼쪽으로만 (110 → 001), 맨 오른쪽의 0은 오른쪽으로만 (011 → 100) 이동할 수 있으며, 이동할 때마다 2칸씩 이동하므로 두 인덱스의 차이는 항상 홀수이다.

$N$이 홀수이고 $M = 1$일 경우 1을 하나만 남겨야 하는데, 1이 맨 왼쪽이나 맨 오른쪽에 있지 않으면 맨 왼쪽 0의 인덱스(1)와 맨 오른쪽 0의 인덱스($N$)의 차이는 짝수이므로 모순이다. 일반성을 잃지 않고 맨 왼쪽에 남긴다고 하면, 그 직전 상태는 011000...0이 되므로 역시 모순이 된다. 따라서 $N$이 홀수, $M$이 1인 경우는 답이 존재하지 않는다.

$M > 1$인 경우는 지울 수 없는 맨 끝의 1을 하나 두고 나머지를 $N - 1$, $M - 1$의 경우로 환원하여 해결할 수 있다.