【Atcoder】順列全探索(ABC150-C問題)【Python】

Atcoderで茶色になるために必要とされる全探索について学んでいます。

全探索の中でも順列を用いるものについて今回はまとめています。

問題(Atcoder Beginner Contest 150 C問題)
1. 問題文
2. 制約
考え方
コード
まとめ

問題(Atcoder Beginner Contest 150 C問題)

問題文

大きさNの順列(1,2,・・・・,N)を並び替えてデキル数列P,Qがある。

大きさNの順列はN!通りある。このうち、Pが辞書順でa番目に小さく、Qが辞書順でb番目に小さいとして、|a-b|を求める。

制約

2<=N<=8
P,Qは大きさNの順列
入力は全て整数

考え方

順列を全探索することで解くことができる。

全探索するためにまずは順列を全列挙する。

順列を全列挙するには、pythonのライブラリであるitertoolsを用いる。

全列挙した順列から、PとQが一致する要素を探し、それぞれ何番目になるかをindexで取得する。

indexで取得したP、Qの順番の差(絶対値)を出力する

コード

#C問題
import itertools #順列を列挙するためのライブラリ
N = int(input())

P = tuple(map(int,input().split()))
Q = tuple(map(int,input().split()))

per = list(itertools.permutations(range(1,N+1))) #1～Nの範囲で順列を全列挙してリストにし、perに代入
p = per.index(P) #全列挙した順列が格納されたperから、Pの順列Pが何番目かを取得
q = per.index(Q) #perから、Qの順列が何番目かを取得
print(abs(p-q)) #pとqの差の絶対値を出力

#C問題

import itertools #順列を列挙するためのライブラリ

N = int(input())

P = tuple(map(int,input().split()))

Q = tuple(map(int,input().split()))

per = list(itertools.permutations(range(1,N+1))) #1～Nの範囲で順列を全列挙してリストにし、perに代入

p = per.index(P) #全列挙した順列が格納されたperから、Pの順列Pが何番目かを取得

q = per.index(Q) #perから、Qの順列が何番目かを取得

print(abs(p-q)) #pとqの差の絶対値を出力

まとめ

itertoolsを使うことで順列や組み合わせを扱うことができます。

全探索をすると計算量が多くなり、Atcoderで提出するとTLEとなりやすいです。

C問題を解くためには、計算量を減らせる工夫を合わせて考える必要があります。

今回はNの範囲が狭く、計算量も少なかったため全探索でも正答することができます。