問題
D – 阿弥陀
回答
30点回答
前回の方法で一つのあみだくじであれば解くことができるので、次にあみだくじを複数つなげることを考えます。
一つのあみだくじの開始地点から到達地点への変換を辞書に記憶し、この辞書による変換を複数回一つ...
yottagin.com
2019-12-04 13:57
問題
D – 阿弥陀
回答
ダブリング
ダブリングとは、 2倍することをlogN 回繰り返すことで Nに到達できることを利用する手法です。
あみだくじにはダブリングの手法が適用できます。
ちゃんと解くためには、「 冪乗法は結合法則を満たせば使用できる（群は定義より満たす） 」ということを理解していなければならないので、私にはまだ早い。
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)