ABC150 C - Count Order を解いた

7569 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク




今回は問題が分かり易い。
いっつも忘れる、permutation どう描くんだっけ?

参考にしつつ、全探索してみた。
2 < N < 8 なので助かった。

CountOrder.py
n = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

P = "".join(list(map(lambda x:str(x),P)))
Q = "".join(list(map(lambda x:str(x),Q)))

from itertools import permutations
i = 1
dic={}
for nums in permutations(range(1,n+1)):#O(40000)
    #print(nums)
    nums = list(nums)
    nums = "".join(list(map(lambda x:str(x),nums)))#O(8)
    dic[nums] = i
    i += 1

print(abs(dic[P]-dic[Q]))#114ms

permutation は辞書順で出してくれる。
だから出力と、何番目に出力したのかを記録する i があれば
テーブルは簡単にできる。

後は引き算だけだ!!

あれから。。再チャレンジ

abc150c.py
N = int(input())
P = list(input().split())
P = "".join(P)
Q = list(input().split())
Q = "".join(Q)
from itertools import permutations
lis = []

for i in permutations(map(str,range(1,N+1)),N):
    lis.append("".join(i))

print(abs(lis.index(P)-lis.index(Q)))#40ms

少しだけ深化できたかも。