[Python] ABC013 D　10点回答

問題

D – 阿弥陀

10点回答

10点の回答を理解するのに1時間ぐらいかかった…。

あみだくじは、「置換」の問題として考えることができます。

横線は「互換」に相当して、その「互換」の組み合わせ、つまり「リストの要素の交換」で単体のあみだくじは考えることができます。

「入力例1」の場合、以下のようなコードで、それぞれの開始地点に対応する到着地点を得ることができます。

import collections

N, M, D = map(int, input().split())
A = list(map(int, input().split()))

amida = list(range(1, N+1))
for a in A:
    amida[a], amida[a-1] = amida[a-1], amida[a]

print(amida)

問題では、 「最終的に下端で左から何番目の縦線に行き着くか 」を考えるので、上とは逆に、それぞれの下端の地点から開始地点へのあみだくじで求めることができます。

import collections

N, M, D = map(int, input().split())
A = list(map(int, input().split()))

amida = list(range(1, N+1))
for a in reversed(A):
    amida[a], amida[a-1] = amida[a-1], amida[a]

print(amida)