この記事で使うアルゴリズム
動的計画法
深さ優先探索
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja
この問題は動的計画法で解くことができます。
方針
全探索の計算量はO(N!)
となり間に合いません。そこで動的計画法を用います。
経路は全ての頂点を通るため、頂点0
からそれ以外の全ての頂点を通ったのち、頂点0
に戻るというように考えて問題ありません。
集合S
に訪問済みで頂点v
にいるとした時の頂点0
まで戻るパスを考え、その経路長をdp[S][v]
として計算します。ここでS
が集合を表すため、実装上の工夫としてS
を長さV
のビット列として考えます(1
は訪問済み、0
は未訪問とします)。
コード
1 | V, E = map(int, input().split()) |
参考
アルゴリズムの多くはプログラミングコンテストチャレンジブック(通称、アリ本)のP173-175を参考にさせていただきました。
リンク
記事情報
- 投稿日:2020年5月21日
- 最終更新日:2020年5月21日