AtCoder Regular Contest 145 A問題 AB Palindrome

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

${\tt A}, {\tt B}$ からなる長さ $N$ の文字列 $S$ が与えられる.

以下の操作を $0$ 回以上行うことにより, $S$ を回文にすることは可能か?

$S$ の隣接する2つの文字を ${\tt AB}$ に置き換える.

制約

$2 \leq N \leq 2 \times 10^5$
$S$ は ${\tt A}, {\tt B}$ からなる長さ $N$ の文字列.

解法

文字列 $T$ と $1 \leq i \leq |T|$ に対して, $T_i$ で $T$ の $i$ 文字目を表すことにする.

$N=2$ のときは操作をしてしまうと $S={\tt AB}$ になってしまい, 回分にならない. 従って, 最初の状態で回分かどうかを判定すれば良い. つまり, $S={\tt AA}$ か $S={\tt BB}$ であるかどうかを判定すれば良い.

$N \geq 3$ とする. このとき, 可能であるための必要十分条件は $(S_1, S_N) \neq ({\tt A}, {\tt B})$ である. これを証明する. ここで, $i$ 文字目と $(i+1)$ 文字目を ${\tt AB}$ に置き換える操作を操作 $i$ と呼ぶことにする.

のとき: 以下のように上から操作すると, にすることができる.
- 操作 $1$ $\to$ 操作 $2$ $\to \cdots$ 操作 $(N-2)$
- 操作 $1$ $\to$ 操作 $2$ $\to \cdots$ 操作 $(N-3)$
- $\vdots$
- 操作 $1$
のとき: 以下のように上から操作すると, にすることができる.
- 操作 $(N-2)$ $\to$ 操作 $(N-3)$ $\to \cdots$ 操作 $2$
- 操作 $(N-2)$ $\to$ 操作 $(N-3)$ $\to \cdots$ 操作 $3$
- $\vdots$
- 操作 $(N-2)$
$(S_1, S_N)=({\tt B}, {\tt A})$ のとき: 操作 $1$ を施すと, $(S_1, S_N)=({\tt A}, {\tt A})$ の場合に帰着できる.
$(S_1, S_N)=({\tt A}, {\tt B})$ のとき: どのような操作を施したとしても, $(S_1, S_N)=({\tt A}, {\tt B})$ の状況は変わらず, これは明らかに回分ではない.