【競プロ】ダブリングの使用例【Python】

競プロの問題を解いていてダブリングという手法が出てきたのですが、理解するのに苦労し、今後また使用したい際に見返すためのメモです。

使える場面

同じ操作を繰り返し行う際、N回目（Nはとても大きい）の結果を知りたいとき

O(N)オーダーの計算量をO(logN)に減らすことができるらしい、すごい

使い方

コードで書くと要素iに対する2^k回後の操作した値は

dp[k][i] = dp[k-1][dp[k-1][i]]

これだけだと意味が分からなすぎるので問題と一緒に見ます。

ABC136 D – Gathering Children

LとRの文字列Sとその文字列の長さと同じ長さのマス、マスにはそれぞれ子供が1人ずついる

i番目のマスにいる場合、Sのi文字目がLなら左へ、Rなら右へ移動

10^100回移動した後の各マスの子供の数を出す問題。

10^100回移動というくそデカ数字とLRの文字列Sは変化しないのでi番目のマスからの移動先は常に同じ、同じ操作を繰り返すのでダブリングが使える。

10^100回移動するが、収束まで一番時間がかかるパターンは文字列が1文字目がR残りがすべてLの場合なので最悪でも10^5回の移動で収束、10^100と10^5はどちらも偶数なので10^5回より後の移動であればどれも同じになるはずです。

dp[k][i]をマスiから2^k回移動した後のマスの位置とします。

例として文字列SをRLLLLLLとおいてみます。

1回目の操作後つまり2^k=1,k=0の値をまずは埋めてみます。

次にk=1,2^kが2の時の値を考えます。これも1の次なので考えやすいですが、最初のコードの通りに考えると

dp[k][i] = dp[k-1][dp[k-1][i]]

マスiの2^1回移動後のマスは「マスiの2^0回移動後のマス」の2^0回移動後のマス(k=1)

です。まだ意味わかんないですね。

k=1の値をk=0の値のみから導き出せるのがなんとなくもやっとするかもですが（自分はしました）、同じ操作をしているというのがみそなので何回目にマスiに来ようともその後行くマスの位置はそこから何回移動するかだけに依存しています。k=1を埋めると次の表

次にk=2を考えてみます。マスiから2^k=4回移動した後のマスはマスiから2^(k-1)=2回移動したのちにたどり着いたマスからさらに2^(k-1)=2回移動したマスです。つまりどちらもk=1の値を使用して求めることができます。

i=6のマスに着目してみましょう。k=2、つまり4回移動するというのはマス6から2回移動し、そこからさらに2回移動する、と同じです。2回移動するというのはk=1の時でありここでk=1の値を使用することができます。

マス6から2回移動すると表のk=1からマス4に移動します。マス4から2回移動すると同じく表のk=1からマス2に移動することがわかります。つまりマス2がマス6から4回移動したあとのマスです。

k=3も埋めます。やり方は同じです。

改めて式を一般化して説明すると

マスiの2^k回移動後のマスは「マスiの2^(k-1)回移動後のマス」から2^(k-1)回移動後のマス

です。なんとなくわかってきた気がします。

今回は10^5回までの移動を考えればいいので2^17までの移動を考えればOKです。

最後に収束した後の各マスの数を数えれば答えになります。

s = input()
n = len(s)

log = 18
dp = [[0] * n for _ in range(log)]

for i in range(n):
    dp[0][i] = i+1 if s[i] == "R" else i-1

for k in range(1, log):
    for i in range(n):
        dp[k][i] = dp[k-1][dp[k-1][i]]

ans = [0] * n
for i in dp[log-1]:
    ans[i] += 1

print(*ans)