Atcoderで茶色になるために必要とされる全探索について学んでいます。
全探索の中でも順列を用いるものについて今回はまとめています。
問題(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の順番の差(絶対値)を出力する
コード
1 2 3 4 5 6 7 8 9 10 11 |
#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の範囲が狭く、計算量も少なかったため全探索でも正答することができます。
コメント