ARC059D アンバランス/Unbalanced - seriruの技術屋ブログ

AtCoder Regular Contest 059 D アンバランス/Unbalanced

与えられる文字列 $s$ において, 部分文字列 ( $sub$ とする)が以下の条件を満たすとき, その位置を示せ。

部分点は $2 \leq [s$ ] $\leq 100$ の場合は O(n³) で全ての部分文字列を列挙して探索すればよいです。

次に満点回答を考えます。

満点回答では10⁵を考える必要があるため、全列挙するO(n³)の解法は使えません。

ここで発想を、すべての部分文字列を調べる、から、条件を満たす部分文字列のパターンを考える、に転換させます。

では条件(長さ2以上で過半数の文字が同じ)を満たす文字列のパターンはどのようなものでしょうか？

小さいほう( $sub \geq 2$ )から考えてみます。

同じ文字をX, X以外の文字をYとすると,
$sub = 2$ のとき , XとYで表せる文字列のパターンで条件を満たすのは,

となります。同様に $sub = 3$ のとき

XXX, YXX, XYX, XXY

$sub = 2$ と被るものを取り除くと

XYX

のみになります。

$sub \geq 4$ の文字列は $sub = 2$ と $sub = 3$ から生成できるので, 考えるべきパターンは, $sub = 2$ と $sub = 3$ だけということに分かります。

以上より文字列 $s$ より $i = i+1$ , $i = i+2$ が等しいときに条件を満たすことがわかりました。

sample code:

転換って書いたけど自明なのかという疑問