[全探索：順列全探索]を抑える pythonで競プロ

Qiitaで紹介されていた初中級者が解くべき過去問精選 100 問をpython解いてみようという試みです。

第4弾として、[全探索：順列全探索]の項の問題を解いていきます。

第15問 : Average Length

問題文

問題文

座標平面上に N 個の町があります。町 i は、座標 ( x_i​ , y_i​ ) に位置しています。町 i と町 j の間の距離は √(x_i-x_j)​² +(y_i-y_j)​²です。

これらの町を全て 1 回ずつ訪れるとき、町を訪れる経路は全部で N! 通りあります。1 番目に訪れる町から出発し、2 番目に訪れる町、3 番目に訪れる町、…、を経由し、N 番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。これらの N! 通りの経路の長さの平均値を計算してください。

制約条件

• 2≤N≤8
• −1000≤x_i​≤1000
• −1000≤y_i​≤1000
• (x_i​,y_i​)≠(x_j​,y_j​) ( i≠j のとき)
• 入力中の値はすべて整数である。

https://atcoder.jp/contests/abc145/tasks/abc145_c

解答

説明

全ての順列のパターンは、 itertools.permutationsによって作成することが可能です。

順列さえ作成してしまえば、後は順番に距離を求めていけば答えになります。

第16問 : Count Order

問題文

問題文

大きさ N の順列 ((1, 2, …, N) を並び替えてできる数列) P, Q があります。

大きさ N の順列は N! 通り考えられます。このうち、P が辞書順で a 番目に小さく、Q が辞書順で b 番目に小さいとして、∣a−b∣ を求めてください。

制約条件

• 2≤N≤8
• P, Q は大きさ N の順列である。
• 入力は全て整数である。

https://atcoder.jp/contests/abc150/tasks/abc150_c

解答

説明

1~Nまでの数で作成できる順列を先に作ってソートしておき、P,Qが何番目と一致するかを後で判定する方針で実装しました。

itertools.permutationsで帰ってくる一つ一つのパターンはtupleなので、P,Qも同様にtupleで持っておくことによってindexで一致するパターンを探せるようにしています。

第17問 : 8 Queens Problem

問題文

問題文

8 クイーン問題とは、8×8 のマスから成るチェス盤に、どのクイーンも他のクイーンを襲撃できないように、8 つのクイーンを配置する問題です。チェスでは、クイーンは次のように８方向のマスにいるコマを襲撃することができます。

すでにクイーンが配置されている k 個のマスが指定されるので、それらを合わせて８つのクイーンを配置したチェス盤を出力するプログラムを作成してください。

制約条件

• 入力に対する解はただ１つ存在する。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_A&lang=ja

解答

説明

バックトラック法という手法を用いて実装しました。

キーとなるのが34~35行目です。条件を満たすマスが一つ見つかった時に、そのマスにQを置くことを確定させてしまい、その状態でその後の探索を行います。

Qを確定させた状態での探索が完了すると、その位置にQを置かない状態に戻して以降の探索を行います。これを再起的に行うことによって、効率良く全てのパターンを洗い出す事ができます。

8クイーン問題に関しては、別記事に纏めましたので良ければ読んでみて下さい。（8クイーン問題について）

まとめ

順列全探索に関しては、Pythonだとitertools.permutations一発で完結してしまうため、他言語より難易度は優しいのかなと感じました。

バックトラック法に関しては、昔数独ソルバー作ってみた時に使っていたので、懐かしいなと思いながら実装していました。数独に関しても気が向いたら記事にしてみます。

次回は、[二分探索]を解いていきます。