다다스와 모그의 이진수열

문자열 $C$에 대해 Constraints 섹션에서 정의한 값 $H_0(C),H_1(C),\ldots,H_N(C)$를 생각하자. 각 문자를 하나 읽을 때 값은 정확히 $1$만큼 증가하거나 감소한다.

각 $i$ ($1 \leq i \leq N$)에 대해

$$E_i(C)=\min(H_{i-1}(C),H_i(C))$$

로 정의한다. $E_i(C)=x$라는 것은 $i$번째 문자를 읽을 때 정수 $x$와 $x+1$ 사이를 한 번 지나갔다는 뜻이다.

구간 $[l,r]$에 $0$과 $1$이 같은 개수만큼 들어 있다는 조건은 $H_{l-1}(C)=H_r(C)$와 같다. 연산을 수행하면 이 구간에서 지나간 경계들의 순서만 반대가 된다. 따라서 $E_l(C),E_{l+1}(C),\ldots,E_r(C)$의 순서가 뒤집히며, 다른 $E_i(C)$는 변하지 않는다.

그러므로 각 정수 $x$에 대해 $x$와 $x+1$ 사이를 지나간 횟수는 변하지 않는다. 즉, $A$를 $B$로 바꿀 수 있으려면 다음 두 멀티셋이 같아야 한다.

$$\{E_1(A),E_2(A),\ldots,E_N(A)\},\qquad \{E_1(B),E_2(B),\ldots,E_N(B)\}$$

이 조건은 충분하기도 하다. $E(A)$를 현재 수열, $E(B)$를 목표 수열이라고 하고 왼쪽부터 같은 값으로 만들어 보자.

현재 $i-1$번째 위치까지 같게 만들었다고 하자. $E_i(A)=E_i(B)$라면 그대로 다음 위치로 넘어간다.

두 값이 다르다면 현재 높이에서 $E_i(A)$가 나타내는 경계와 $E_i(B)$가 나타내는 경계는 서로 반대 방향에 있다. 현재 경로는 먼저 잘못된 방향으로 움직였으므로, 목표 경계를 처음 지날 때에는 현재 높이에서 목표 방향으로 떠난다. 그 목표 경계를 두 번째로 지날 때에는 다시 현재 높이로 돌아온다.

따라서 $E_i(B)$가 현재 수열의 $i$번째 위치 이후에서 두 번째로 나타나는 위치를 $j$라고 하면, 원래 문자열의 구간 $[i,j]$은 시작 높이와 끝 높이가 같다. 즉, 이 구간에는 $0$과 $1$이 같은 개수만큼 들어 있어 연산할 수 있다.

이 구간에 연산하면 $E_i(A),E_{i+1}(A),\ldots,E_j(A)$의 순서가 뒤집힌다. 마지막 값이었던 $E_j(A)=E_i(B)$가 $i$번째 위치로 오므로, 새롭게 $i$번째 위치까지 목표와 같아진다.

가능 조건이 성립하면 필요한 두 번째 등장 위치는 항상 존재한다. 각 위치마다 뒤쪽을 선형으로 탐색하고, 찾은 구간을 직접 뒤집으면 된다. 탐색과 뒤집기에 각각 $O(N)$ 시간이 들고 이를 $N$번 이하 수행하므로 전체 시간 복잡도는 $O(N^2)$이다. 필요한 배열과 답을 저장하는 메모리 복잡도는 $O(N)$이다.

각 위치에서 연산을 많아야 한 번 수행하므로 출력하는 연산 수는 $N$ 이하이다.

Solution written by GPT5.6