過去問精選100 問全探索：順列全探索【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210322214723p:plain
こちらの記事で紹介されている初中級者が解くべき過去問精選100 問を解いていきます。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

この記事は全探索：順列全探索編です。
順列全探索についての過去の記事はこちらです。
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

ABC145 C - Average Length

C - Average Length

問題文

座標平面上にN個の町があります。町iは、座標 (xi, yi) に位置しています。町iと町jの間の距離は √(xi−xj)^2+(yi−yj)^2です。
これらの町を全て1回ずつ訪れるとき、町を訪れる経路は全部でN!通りあります。
1番目に訪れる町から出発し、2番目に訪れる町、3番目に訪れる町、…、を経由し、N番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。これらのN!通りの経路の長さの平均値を計算してください。

制約

・2≤N≤8
・−1000≤xi≤1000
・−1000≤yi≤1000
・(xi,yi)≠(xj,yj)(i≠jのとき)
・(21:12 追記) 入力中の値はすべて整数である。

解答例

import itertools
import math

n = int(input())
x = []
y = []
for i in range(n):
    xx, yy = map(int,input().split())
    x.append(xx)
    y.append(yy)

per_list = list(itertools.permutations(range(n))) # nまでの順列を作成

sum_dist = 0
for i in per_list:
    for j in range(n-1):
        x2 = (x[i[j + 1]] - x[i[j]]) ** 2
        y2 = (y[i[j + 1]] - y[i[j]]) ** 2
        sum_dist += math.sqrt(x2 + y2)

ans = sum_dist / len(per_list)

print(ans)

解説

順列全探索の問題です。

itertoolsモジュールをインポートして順列（permutations）を作成します。
per_listにはN個の町を訪れる経路の順列が格納されます。

あとは2重ループでsum_dist変数にすべての経路の距離を足していきます。

2重ループが抜けたらper_listの個数で割って平均をans変数に代入すればOKでした。

ABC150 C - Count Order

C - Count Order

問題文

大きさNの順列 ((1, 2, ..., N)を並び替えてできる数列) P,Qがあります。
大きさNの順列はN!通り考えられます。このうち、Pが辞書順でa番目に小さく、Qが辞書順でb番目に小さいとして、|a−b|を求めてください。

注記

2つの数列X,Yについて、ある整数kが存在してXi=Yi (1≤i

制約

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

解答例

import itertools

n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))

per_list = list(itertools.permutations(range(1,n+1))) # nまでの順列を作成

a = 0
a_count = 1
for i in per_list:
    can = 1
    for j in range(n):
        if p[j] == i[j]:
            continue
        else:
            can = 0
            a_count += 1
            break
    if can == 1:
        a = a_count
        break

b = 0
b_count = 1
for i in per_list:
    can = 1
    for j in range(n):
        if q[j] == i[j]:
            continue
        else:
            can = 0
            b_count += 1
            break
    if can == 1:
        b = b_count
        break
    
ans = abs(a - b)

print(ans)