競プロ初中級者100問

ABC150C Count Order

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

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

この問題は全探索を用いて解くことができます。

方針

制約条件から全探索で十分に間に合います。辞書順に順列を全探索し、P, Qがそれぞれ何番目に出現したかを記録すれば良いです。

itertools.permutationsに辞書順でソートされたシーケンスを渡せば、順列を辞書順に取得できるイテレータが生成されます。

コード

1
2
3
4
5
6
7
8
9
10
11
12
from itertools import permutations
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

for i,p in enumerate(permutations(range(1,N+1))): # (1,2,3,..)のように辞書順に並んでいるシーケンスを渡す
    if p==P:
        a = i
    if p==Q:
        b = i

print (abs(a-b))

記事情報

  • 投稿日：2020年5月28日
  • 最終更新日：2020年5月28日