Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 136 A問題 A ↔ BB

AtCoder ARC ARC136 A問題 300 pts

問題

提出解答

問題の概要

${\tt A}, {\tt B}, {\tt C}$ からなる長さ $N$ の文字列 $S$ が与えられる. $S$ に対して, 以下の操作を $0$ 回以上行ってできる文字列のうち, 辞書式最小のものを求めよ.

$S$ にある $'{\tt A}'$ を $'{\tt BB}'$ に置き換える.
$S$ にある $'{\tt BB}'$ を $'{\tt A}'$ に置き換える.

制約

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

解法

まず, 操作によって, $'{\tt C}'$ が変化に寄与することはない. そこで, $S$ を $'{\tt C}'$ で区切って, $'{\tt A}', '{\tt B}'$ のみからなると考えても良い. また, $'{\tt A}', '{\tt B}'$ は $'{\tt C}'$ よりも辞書式の意味で小さいので, 区切った文字列内での最小化を目指す.

辞書式の意味で, $'{\tt A}'$ は $'{\tt B}'$ よりも前である. そして, $'{\tt A}'$ を $2$ 点, $'{\tt B}'$ を $1$ 点としたとき, $'{\tt A}', '{\tt B}'$ からなる文字列において, 同じ点数である2つの文字列は操作によって互いに推移可能である.

$X$ 点の文字列において, 辞書式最小なのは, $\displaystyle Y=\left \lfloor \dfrac{X}{2} \right \rfloor$ として,

$X$ が奇数のとき, $\underbrace{{\tt A} \oplus \dots \oplus {\tt A}}_Y \oplus {\tt B}$ .
$X$ が偶数のとき, $\underbrace{{\tt A} \oplus \dots \oplus {\tt A}}_Y$ .

である.

これをそれぞれ区切った文字列ごとにみて, ${\tt C}$ を結合させることにより, 計算量は $O(N)$ である.