ABC013 D 阿弥陀

内容

Atcoder Beginner Contest 013 D問題 「阿弥陀」をpythonで解いた。

問題

阿弥陀くじが一つ与えられる。 そのあみだくじを、D個縦につなげる。 つなげたあと、各スタート地点からたどり着く場所を求めろ。 atcoder.jp

考えたこと

• あみだくじは、同じものをD個つなげる。
• あみだくじ一つ(D=1)の時は、O(M)くらいでシミュレーションできる。
• つなげる数は、D(10**9)なので1回のシミュレーションをD回繰り返すのは無理。

  ポイント

• 効率的にシミュレーションしたい。

  • ダブリングする!

    • 2ⁿ回の移動で、各startからどこにたどり着くかを計算しておく。

    • log2(D)程度のシミュレーション回数でD回分の移動を計算できる。

      • D=9なら、2³+2⁰なので、9回のシミュレーションを二回の計算で行える。

• これで、D回のシミュレーションをO(10⁹)からO(log2(10**9))まで減らせるので間に合う。

  • (log2(10**9)は30程度)

実装

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

A = list(map(lambda x:int(x)-1,input().split()))

#一回分シミュレーションをする。
dest=list(range(N))
for a in A:
    #横線があると、aとa+1が入れ替わる
    dest[a],dest[a+1] = dest[a+1],dest[a]

#初回の行先(dest[key]=val, startがkeyの時に、valにたどり着く
dest={v:i for i,v in enumerate(dest)}

#ダブリングする DUB[i][j]= startがiで、2**i回移動する時に、たどり着く場所
DUB=[[-1]*N for _ in range(D.bit_length())]

#初期化(一回分のシミュレーションの結果で、DB[0]を初期化する
for key,val in dest.items():
    DUB[0][key]=val

#DUBを埋めていく。 D回の移動を求めるのには、2**(D.bitlen-1)まで必要。
#(考え方):2**(i-1)回の移動を、2回繰り返すと2**iの移動になる。

for i in range(1,D.bit_length()):
    for key in range(N):
        DUB[i][key] = DUB[i-1][DUB[i-1][key]]

#求めたダブリングの結果を使って、答えを求める。

ans=list(range(N))

for i in range(D.bit_length()):
    if  D>>i &1:#Dをsum(2**x)で表す時に2**iを使う
        for key in range(N): #2**i回の移動を適応する。
            ans[key]=DUB[i][ans[key]]

print("\n".join(map(lambda x:str(x+1),ans)))

終わりに

• 備忘録