[Python] ABC013 D 100点

問題

D – 阿弥陀

回答

ダブリング

ダブリングとは、 2倍することをlogN 回繰り返すことで Nに到達できることを利用する手法です。

繰り返し 2 乗法 ( バイナリ法 )

あみだくじにはダブリングの手法が適用できます。

置換の冪乗

ちゃんと解くためには、「 冪乗法は結合法則を満たせば使用できる（群は定義より満たす） 」ということを理解していなければならないので、私にはまだ早い。

回答はこちらのほぼ真似です。

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

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

# D<=10**9 < 2 ** 30　なので、
# ダブリングを使うことで30通りの移動リスト考えるだけで良い。
k = D
move_list = [[int(i) for i in range(N)] for _ in range(30)]
for i in range(N): 
    move_list[0][i] = amida[i]
for k in range(1, 30):
    for i in range(N):
        move_list[k][i] = move_list[k-1][move_list[k-1][i]]

# ダブリングのため立っているビットの算出
k = 0
l = D
bin_index = []
while l > 0:
    if l % 2 == 1: 
        bin_index.append(k)
    k += 1
    l //= 2

# ビットの立っている部分だけリストに従い移動
for i in range(N):
    now = i
    for k in bin_index:
        now = move_list[k][now]
    print(now + 1)