AtCoder Beginner Contest 043 / Regular Contest 059 D. アンバランス：解法と実装
8月13日に行われた、AtCoder Regular Contest 059に参加しました。この記事では、このコンテストおよびAtCoder Beginner Contest 043で共通して出題された、D: アンバランス / Unbalanced - AtCoder Regular Contest 059 | AtCoderの解き方とそのPython 3による実装について、復習を兼ねて書きます。
問題の趣旨
文字列tが2以上の長さlをもち、tに含まれるある文字の個数がlの過半数であるときに限り、tはアンバランスであるということにする。与えられる文字列sにアンバランスである部分文字列が存在すれば、そのような部分文字列を一つ選んでその位置を答えよ。存在しなければその旨を報告せよ。
解き方
部分点解法
文字列sの長さNが小さければ、部分文字列を列挙し、それぞれがアンバランスであるかを判定するという愚直な全探索により解けます。私がコンテスト中に実装できたのはこれでした。計算量は程度です。
満点解法*1
アンバランスであるsの部分文字列ならどれを答えにしてもよいので、そのうちなるべく短いものを考えることにしましょう。すると、AおよびBを相異なる適当な文字とすると、"AA"と"ABA"の2パターンを考えれば十分であることがわかります。なるべく短いアンバランスな文字列を考えるので、これらの少なくとも一方の端にいくつかの文字を追加したパターンを考慮する必要はありません。また、"ABBA", "ABBBA"などの、AとAの間に2つ以上のBが含まれるパターンは、アンバランスではありません。よって、sのi番目の文字をと表すと、
または
を満たすiを見つければよいことになります。計算量は
程度です。
