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

この記事は約2分で読めます。

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の順番の差(絶対値)を出力する

コード

まとめ

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

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

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

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

コメント