[Python] ABC013 D 50点

[Python] ABC013 D　10点回答

問題 D - 阿弥陀 10点回答 10点の回答を理解するのに1時間ぐらいかかった…。 あみだくじは、「置換」の問題として考えることができます。 横線は「互換」に相当して、その「互換」の組み合わせ、つまり「リストの要素の交換」で単体のあみだくじは考え...

yottagin.com

2019-12-03 15:06

問題

D – 阿弥陀

回答

30点回答

前回の方法で一つのあみだくじであれば解くことができるので、次にあみだくじを複数つなげることを考えます。

一つのあみだくじの開始地点から到達地点への変換を辞書に記憶し、この辞書による変換を複数回一つのあみだくじに適用します。

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]

# x番目の縦線から始めるとamida_frm_to[x]で終わる。
amida_frm_to = dict()
for to, frm in enumerate(amida):
        amida_frm_to[frm] = to+1

# 上をD回適用する。
for _ in range(1, D):
    tmp = amida[:]
    for frm, to in amida_frm_to.items():
        tmp[to-1] = amida[frm-1]
    amida = tmp

for a in amida:
    print(a)

50点回答

一つのあみだくじは、互換を組み合わせた置換です。

n個を対象とする置換の総数は n! 通りなので、 あみだくじは少なくとも n! 回でループします。

よって、D を N! で割った余りだけ30点回答の互換を適用すれば答えを得ることができます。

import math

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]

# x番目の縦線から始めるとamida_frm_to[x]で終わる。
amida_frm_to = dict()
for to, frm in enumerate(amida):
        amida_frm_to[frm] = to+1

# D を　N! で割った余りだけループさせる。
d = D % math.factorial(N)
for _ in range(1, d):
    tmp = amida[:]
    for frm, to in amida_frm_to.items():
        tmp[to-1] = amida[frm-1]
    amida = tmp

for a in amida:
    print(a)