【ABC136】D - Gathering Children【ダブリング】
今回はダブリングと呼ばれる手法を使って解いて見ます。
上のブログでも解説されているようにnext[i][v]を定義します。
next[i][v]: vから$2^{i}$ステップで到達できる場所
まずは$i=0$の場合を考えてnext[0][v]を初期化します。
それぞれの場所vに記されたL, Rに従ってLならv-1、Rならv+1をnext[0][v]に格納します。
これ以降は
next[i+1][v] = next[i][next[i][v]](vから$2^{i}$ステップで行ける場所からさらに$2^{i}$ステップ移動する。)
に従って更新していきます。
なぜ2の乗数になっているかは漸化式に値を代入してみれば確認できます。
next[0][v]: vから1ステップで行ける場所(総ステップ数：1)next[1][v] = next[0][next[0][v]]: vから1ステップで行ける場所からさらに1ステップで行ける場所(総ステップ数：2)next[2][v] = next[1][next[1][v]]: vから2ステップで行ける場所からさらに2ステップで行ける場所(総ステップ数：4)
next[1][v]の総ステップ数が2であることを利用しました。
せっかくなのでさらに計算を進めると、
next[3][v] = next[2][next[2][v]]: vから4ステップで行ける場所からさらに4ステップで行ける場所(総ステップ数：8)next[4][v] = next[3][next[3][v]]: vから8ステップで行ける場所からさらに8ステップで行ける場所(総ステップ数：16)next[n+1][v] = next[n][next[3][v]]: vから$2^{n}$ステップで行ける場所からさらに$2^{n}$ステップで行ける場所(総ステップ数：$2^{n+1}$)
以上のようにダブリングしていることが分かりました。
next[i][v]を参照することでvから$2^{i}$ステップ進んだ場所がどこなのかを知ることが出来ました。
では$2^{i}$以外のステップ数進んだ場合を知るにはどうしたらいいのでしょうか？
整数$x$を2進数で展開して下位のビットから走査し1であればnext[i][v]を使って場所を更新していきます。
コードは以下のようになります。
int s = 0; int step = 5; rep(d, MAX-1) { if (step & (1<<d)) s = next[d][s]; } cout << s << " " << S[s] << endl;
上の例では場所0から5ステップ進んだ後の場所を求めています。
5は2進数で表すと101です。一番下位の0ビット目を見ると1なのでまずは1ステップだけ進みます。
そうするとnext[0][0] = aに到達しました。(この場所をaとしました。)
次の1ビット目は0なので無視します。2ビット目が1なのでaから$2^{2}$ステップだけ進みます。
最終地点はnext[2][a]となります。
コード全体は以下にUpしました。
powの計算などにもダブリングが使えるみたいですね。
