Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

ABC043-D アンバランス / Unbalanced 解説

問題

D - アンバランス / Unbalanced

解説

まず自明な全探索解法を考えると思いますが, これは O(|S|^2)なのでTLEします.
ここで探索範囲を少なくしていくことを考えます.
最小のアンバランスな文字列はaaやbbと言った同じ文字が連続するものであることが分かります, そしてもうひとつaaやbbで表現できないものとしてabaやbcbなどの1文字開けて同じ文字が連続するものが存在します.

実はこの2つのみを探索することでアンバランスな部分文字列を判定することができます, 以下に証明を与えます.

まず, 与えられた文字列にアンバランスな部分文字列が存在する場合について考えましょう, このアンバランスな部分文字列をtと置きます.
ここで鳩の巣原理よりtにはかならず上記のいずれかの部分文字列が存在することが分かります.

次に与えられた文字列にアンバランスな部分文字列が存在しない場合について考えます, この場合アンバランスな部分文字列が存在しないので当然上記のいずれかの部分文字列も存在しないことは明らかです.

これで考察は終わりです, 実装しましょう.

コード

Submission #1873337 - AtCoder Beginner Contest 043

感想

エスパーできそう(小並感).