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"に変換できるs∈Snの個数xを求めよ。ただし、操作をどんな順番で施してもよく、またそれぞれの操作を(上記の条件が満たされている限り)何回行ってもよいものとする。
方針
集合Snの要素を全列挙し、それぞれについて"a"に変換できるかを深さ優先探索あるいは幅優先探索により判定すれば解けます。制約条件2≦n≦6からSnの要素数は高々です。それゆえ、(選択する言語・処理系にもよりますが)全列挙によっても制限時間に間に合うでしょう。また、深さ優先探索あるいは幅優先探索は文字列を頂点、実行可能な操作を辺とした有向グラフに対して行うことになります。制約条件からnもqも小さいことが保証されているので、この探索も間に合うでしょう。