この記事で使うアルゴリズム
全探索
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_d
この問題は全探索を用いて解くことができます。
方針
全探索をします。ただし、平行移動の方法が無数にあるので、候補を限定します。
星座のうちある星に対して、写真中のN
個の星のいずれかがマッチする必要があるので、試すべき平行移動はN
通りに絞ることができます。よって計算量はO(MN^2)
で、十分に間に合います。
さらに、写真中のN
個の星をハッシュテーブルで保持しておくことで、O(MN)
に削減することが可能です。
コード
1 | SM = [] |
記事情報
- 投稿日:2020年5月10日
- 最終更新日:2020年5月10日