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

プログラミングとことばに関する話題を中心に,思いついたこと,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に役立った,技術書,参考書,辞書,機器などの紹介も行います.

IndiaHacks 2016 - Online Edition B. Bear and Compressing:PyPy 3による解答例

先日、私はCodeforcesで開催されたIndiaHacks 2016 - Online Edition (Div. 1 + Div. 2)というコンテストに参加しました。この記事では、私が制限時間内に解けた問題の一つである、B. Bear and Compressingという問題について、その解き方とPython 3(ただし、使用した処理系はPyPy 3)による解答例を、自分の頭の整理を兼ねてまとめておきます。

問題の趣旨

長さnの文字列であって、それを構成するどの文字も'a', 'b', 'c', 'd', 'e'あるいは'f'のいずれかであるもの全ての集合Snを考える。また、「文字列の先頭2文字が文字列ai (i = 1, 2, ..., q)に一致するという条件が満たされているときに、その先頭2文字だけを1文字の文字列biに置き換える」という操作fiが与えられる。このときに、{fi}の各操作を施すことにより、最終的に"a"に変換できるsSnの個数xを求めよ。ただし、操作をどんな順番で施してもよく、またそれぞれの操作を(上記の条件が満たされている限り)何回行ってもよいものとする。

方針

集合Snの要素を全列挙し、それぞれについて"a"に変換できるかを深さ優先探索あるいは幅優先探索により判定すれば解けます。制約条件2≦n≦6からSnの要素数は高々6^6=46656です。それゆえ、(選択する言語・処理系にもよりますが)全列挙によっても制限時間に間に合うでしょう。また、深さ優先探索あるいは幅優先探索は文字列を頂点、実行可能な操作を辺とした有向グラフに対して行うことになります。制約条件からnqも小さいことが保証されているので、この探索も間に合うでしょう。

解答例

以下にPyPy 3による、深さ優先探索を用いた解答例を示します。CPython 3を使用したところTime Limit Exceededとなったため、PyPy 3に切り替えたところAcceptedとなりました。なお、コンテスト中は幅優先探索によりました。

疑問点

問題に付けられたタグや、ほかの参加者の方によるツイートによると、この問題は動的計画法でも解けるとのことです。私は動的計画法による解法も考えてみましたが、いまだに思いついていません。

感想

私は制約条件を見て全列挙と幅優先探索による解法を思いつき、それによりすんなりとこの問題を解くことができました。制約条件を踏まえて利用可能なアルゴリズムを考えることの重要性を改めて実感しました。