初中級者が解くべき過去問精選 100 問茶コーダーが解いてみた #4 ( 順列全探索編 )

今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います！

精選100問って何？
過去の記事についてはこちら！！
- 全探索シリーズ
全探索：順列全探索
最後に

精選100問って何？

記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。

今回は第４回目の順列全探索！！

過去の記事についてはこちら！！

全探索シリーズ

全探索：順列全探索

全探索：順列全探索の分野は全部で３問あるので、紹介したいと思います！

15. C - Average Length

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

順列を使用するような問題においては、pythonの場合itertoolsの中にあるpermutationsという機能を使用すると順列を生成することができます。

この問題においては、N個の街を訪れるパターンを列挙したいので、

from itertools import permutations
for i in permutations(n):

とするとN！通りの順列を列挙することができます。
このようにして生成した順列に対して距離をとる（ピタゴラスの定理を用いる）ことで最後に平均をとってAC出来ます！

from itertools import permutations
import math
n = int(input())
d = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for i in permutations(range(n)):
    cnt  = 0
    for j in range(n-1):
        cnt += math.sqrt((d[i[j]][0] - d[i[j+1]][0])**2 + (d[i[j]][1] - d[i[j+1]][1])**2)
    ans += cnt
print(ans/math.factorial(n))

16. C - Count Order

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

これはまさにpermutationsを使用する問題です！
permutationsで生成した順列は常に辞書順で生成されるので、
その中で P が出てきたindexと、Q が出てきたindexを取得しておき、絶対値をとって計算するだけです！！

from itertools import permutations
n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
for i in range(n):
    p[i] -= 1
    q[i] -= 1
a = b = num = 0
for i in permutations(range(n)):
    if p == list(i):
        a = num
    if q == list(i):
        b = num
    num += 1
print(abs(a-b))

17. 8 Queens Problem

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

これはとても難しく自分では解決できず、Twitterのフォロワーさんに助けていただきました。
まず、 permutations によって各行のどの列にQを生成するかを決めます。
そして、縦を調べていき、同じ列にQがなければ次に斜めの判定へと移っていきます。

この斜めの判定方法に苦戦しました...
斜めにQが２つあるということはその２つの結ぶ傾きが±１であるということです。

この判定をしてあげることによってTrueかFalseの判定をすることができ、あとは
64マス分を生成してAC出来ます！！

from itertools import permutations
k = int(input())
rc = [list(map(int,input().split())) for _ in range(k)]
for p in permutations(range(8)): # 各行の何列目にQを置くかの順列を生成
    flag = True # bool判定用
    for i,j in rc:
        if p[i] != j: # p（生成された順列）が入力値の条件を満たしてるか判定する
            flag = False
    if not flag: continue # 上記を満たしていなければさよなら

    for k in range(8):
        for l in range(8):
            if k == l: continue
            if abs(p[k] - p[l]) == abs(k - l):
                flag = False
    if flag:
        for i in p:
            ans = ["."]*8
            ans[i] = "Q"
            print(i,p,ans)
            print("".join(ans))

最後に

順列全探索は最後の問題以外はかなりすんなり解けたのでよかったです！！
今後は二分探索やDFS, BFSが出てくるので投稿頻度が落ちると思いますがご容赦ください...
それではまた #5 でお会いしましょう！！