지우기 2

두 위치 $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$이다.

$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$이다.

이를 $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$이다.

$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$가 모두 가능하다.

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

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

Solution written by GPT6