この記事で使うアルゴリズム
全探索
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e
この問題は全探索を用いて解くことができます。
方針
- 裏返しによって煎餅は反転するだけですので、ある一連の操作があったとして、その操作の順番を入れ替えても結果は変わりません。
- ある特定の列や行を二回裏返すと当然元に戻ります。つまり、ある特定の列や行を二回以上裏返す必要はなく、裏返すか裏返さないかの二択を考えれば良いです。
以上の考察により全探索の計算量はO(2^(R+C))
となることがわかります。しかし、これだと今回の制約では間に合いません。
そこで、縦R
行の固定を考えます。固定のパターンは2^R
通りとなります。縦列が固定されると各行を裏返す返さないを独立に決めることができます。具体的には各行について、裏返した場合と裏返さない場合で良い方を選ぶだけです。
この場合、計算量はO(CR2^R)
となり間に合います。
コード
このような全探索をbit全探索
と呼びます。Python
ではitertools.product
を利用すると良いでしょう。なお、Python
ではTLE
となってしまうため、PyPy
で提出しました。
1 | from itertools import product |
記事情報
- 投稿日:2020年5月19日
- 最終更新日:2020年5月19日