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

問題概要

　文字列 $S$ の部分文字列で、過半数がある１つの文字で構成されているようなものは存在するか。あるならその位置を示せ。

部分点解法( $2$ ≦| $S$ |≦ $100$ )

　全探索をする。任意の２か所について見るのに $O(N^2)$ 、その内側で適する文字列かどうかを判定するのに $O(N)$ 。よって全体で $O(N^3)$ で部分点は獲得できる。

満点解法( $2$ ≦| $S$ |≦ $10^5$ )

　ある文字列が答えの条件を満たす文字列の場合、その部分文字列内には必ず"AA"(Aは任意のアルファベット１文字)か"ABA"(BもAと同じく任意のアルファベット)が存在する。

　このような文字列が存在しなければ、あるアルファベットで挟まれた部分文字列はその間にそれ以外のアルファベットが2つ以上存在することになるため、どのようにしても過半数という壁を超えることはできないからである。

　よって、 $S$ を前から見ていって、"AA"か"ABA"に合致する部分文字列が存在すればその部分文字列は必ず過半数の条件を満たしているから出力すればよい。

　上記を実装して、AC。 $O(|S|)$ 。

怠惰の累積和