지우기 2

최종 문자열에는 서로 다른 두 이웃 문자가 없다. 따라서 최종 문자열은 빈 문자열이거나 한 종류의 문자만으로 이루어진다.

Lemma 1. 길이가 $m$인 문자열 $W$를 전부 지울 수 있는 필요충분조건은 $m$이 짝수이고, 각 문자의 등장 횟수가 $m/2$ 이하인 것이다.

Proof

한 문자를 지울 때마다 다른 문자 하나도 함께 지워야 하므로 필요조건은 자명하다.

충분성은 $m$에 대한 귀납법으로 보인다. 어떤 문자가 정확히 $m/2$번 등장하면 그 문자와 다른 문자가 만나는 경계의 두 문자를 지운다. 모든 문자가 $m/2$번보다 적게 등장하면 서로 다른 아무 이웃 두 문자를 지운다. 두 경우 모두 남은 문자열은 같은 조건을 만족한다.

문자 $X$를 하나 고정하고, 최종 문자열이 $X$만으로 이루어지는 경우를 생각하자. 나머지 두 문자를 $Y,Z$라 하자.

남겨 둘 $X$의 위치를 고르면, 그 사이와 양 끝의 구간은 모두 사라져야 한다.

Lemma 2. 각 구간에서 $Y,Z$의 등장 횟수가 각각 구간 길이의 절반 이하라는 조건만 요구해도, 남길 수 있는 $X$의 최대 개수는 변하지 않는다.

Proof

실제로 전부 지울 수 있는 구간은 Lemma 1에 의해 이 조건을 만족한다.

반대로 이 조건을 만족하는 구간에서 $X$도 절반 이하라면 Lemma 1에 의해 구간 전체를 지울 수 있다. $X$가 절반보다 많다면 모든 $Y,Z$를 $X$와 하나씩 지울 수 있으므로, 그 구간에는 $X$만 남는다.

따라서 이 조건 아래에서 $k$개의 $X$를 남길 수 있다면 실제 연산으로도 적어도 $k$개의 $X$를 남길 수 있다. 그러므로 최대값은 변하지 않는다.

이 최대값을 $M_X$라 하자.

$S[1\ldots i]$에서 $Y,Z$의 등장 횟수를 각각 $Y_i,Z_i$라 하고, $S_i=X$인 위치 $i$에 대해 $u_i=i-2Z_i$, $v_i=i-2Y_i$를 정의한다.

두 위치 $j<i$의 $X$를 연속해서 남길 수 있으려면 그 사이 구간이 Lemma 2의 조건을 만족해야 한다. 이는 정확히 $u_j<u_i$, $v_j<v_i$, $j\not\equiv i\pmod 2$와 같다.

첫 번째로 남는 $X$의 위치 $i$는 $i$가 홀수이고 $u_i>0$, $v_i>0$이어야 한다. 또한 $U=N-2Z_N$, $V=N-2Y_N$라 하면 마지막으로 남는 $X$의 위치 $i$는 $i\equiv N\pmod 2$, $u_i\le U$, $v_i\le V$를 만족해야 한다.

따라서 $dp_i$를 위치 $i$의 $X$를 마지막으로 남길 때 남는 $X$의 최대 개수라고 두면, 이전 위치 $j$는 $j<i$, $u_j<u_i$, $v_j<v_i$를 만족하고 $i,j$의 홀짝이 달라야 한다. 이는 인덱스, $u$, $v$에 대한 3차원 dominance DP이므로 CDQ 분할 정복을 사용하면 $O(N\log^2 N)$에 $M_X$를 구할 수 있다.

Lemma 3. $S_i=X$인 위치들만 보면, $u_j<u_i$와 $v_j<v_i$가 성립할 때 항상 $j<i$이다.

Proof

$S[1\ldots i]$의 $X$의 개수를 $X_i$라 하면 $u_i+v_i=2X_i$이다.

$X$가 등장하는 위치만 보면 $X_i$는 원래 위치 순서대로 엄격히 증가한다. 따라서 $u_j<u_i$와 $v_j<v_i$이면 $u_j+v_j<u_i+v_i$이고, 곧 $X_j<X_i$이므로 $j<i$이다.

Lemma 3에 의해 인덱스 조건은 필요 없다. 점들을 $u$ 순서로 처리하면서 $v$에 대한 dominance 최댓값을 Fenwick Tree로 관리하면 $M_X$를 $O(N\log N)$에 구할 수 있다. 홀짝이 다른 점에서만 전이하도록 두 경우를 따로 관리한다.

이를 $X=\texttt{A},\texttt{B},\texttt{C}$ 각각에 대해 수행한다.

이제 문자 $X$가 전체 문자열에 $x$번 등장한다고 하자. 최종 문자열이 $X^k$라면 연산 한 번마다 길이가 $2$씩 줄어드므로 $k\equiv N\pmod 2$이다. 또한 $X$ 하나를 지우려면 $X$가 아닌 문자가 하나 필요하므로 $k\ge 2x-N$이다.

따라서 가능한 양의 길이의 최솟값은 $N$이 홀수이면 $L_X=\max(2x-N,1)$, $N$이 짝수이면 $L_X=\max(2x-N,2)$이다.

Lemma 4. $M_X>0$이면 가능한 길이는 정확히 $L_X,L_X+2,\ldots,M_X$이다.

Proof

$X^k$가 가능하고 $k>L_X$라고 하자. 최종적으로 남은 $k$개의 $X$ 사이와 양 끝의, 모두 지워진 구간을 $G_0,G_1,\ldots,G_k$라 하자.

$G_r$의 길이를 $m_r$, 그 안의 $X$의 개수를 $x_r$라 하면 $d_r=m_r/2-x_r$는 음이 아닌 정수이다. 또한 $\sum d_r=(N-2x+k)/2>0$이므로 어떤 $d_r$는 양수이다.

그 구간이 포함되도록 서로 이웃한 생존 $X$ 두 개도 함께 지우면, 합쳐진 새 구간에서는 세 문자 모두 길이의 절반 이하로 등장한다. Lemma 1에 의해 새 구간 전체를 지울 수 있으므로 $X^{k-2}$도 가능하다.

이를 반복하면 $L_X,L_X+2,\ldots,M_X$가 모두 가능하다.

따라서 $M_X>0$일 때 $X$만으로 이루어진 최종 문자열의 개수는 $(M_X-L_X)/2+1$이다.

빈 문자열은 Lemma 1에 의해 $N$이 짝수이고 $2\max(\#A,\#B,\#C)\le N$일 때만 가능하다. 세 문자에 대한 개수를 더하고, 빈 문자열이 가능하면 $1$을 더하면 답이다.

따라서 전체 시간복잡도는 $O(N\log N)$이다.

Solution written by GPT6