読者です 読者をやめる 読者になる 読者になる

はむ吉(のんびり)の練習ノート

主にプログラミングについて、思いついたことや、試してみたこと、学んだことを、覚え書きを兼ねてまとめます。

AtCoder Beginner Contest 043 / Regular Contest 059 D. アンバランス:解法と実装

AtCoder 競技プログラミング プログラミング

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が小さければ、部分文字列を列挙し、それぞれがアンバランスであるかを判定するという愚直な全探索により解けます。私がコンテスト中に実装できたのはこれでした。計算量はO(N^3)程度です。

満点解法*1

アンバランスであるsの部分文字列ならどれを答えにしてもよいので、そのうちなるべく短いものを考えることにしましょう。すると、AおよびBを相異なる適当な文字とすると、"AA"と"ABA"の2パターンを考えれば十分であることがわかります。なるべく短いアンバランスな文字列を考えるので、これらの少なくとも一方の端にいくつかの文字を追加したパターンを考慮する必要はありません。また、"ABBA", "ABBBA"などの、AとAの間に2つ以上のBが含まれるパターンは、アンバランスではありません。よって、si番目の文字をs_iと表すと、s_i = s_{i + 1}またはs_i = s_{i + 2}を満たすiを見つければよいことになります。計算量はO(N)程度です。

Python 3による実装

部分点解法


満点解法


感想

コンテスト中は、何か適当なアルゴリズムで「殴る」ことばかり考え、満点解法に至りませんでした。これはよくない癖だと思います。何か有名なアルゴリズムを使うにせよ、何のひねりもなしにとは限らないはずです。それぞれの問題に向き合い、頭や手を動かしてみることは大事だと改めて感じ増しました。

*1:解説PDFを参考にしています。