ダブリング
おきもち
https://gyazo.com/f044111ccfe8f71aeffa2bc25dc1f809
例えば一直線上謎すごろくで、85マス先にあるゴールにちょうど行きたいとします（謎の設定） 。
手持ちが
1マス進む
だけのとき、自分がゴールに着くには、85ターンが必要です。
計算量的には、距離を$ Nとすると、$ O(N)となります。
手持ちが
1マス進む
2マス進む
4マス進む
8マス進む
....
$ 2^nマス進む
のとき、選択肢をうまいこと使えば今回の場合だと 64 + 16 + 4 + 1 の4回のターンでゴールへ着くことができます。
計算量的には、距離を$ Nとすると、$ O(logN)になります。
利用例
これを知った上で、「自分から木をN個さかのぼった頂点の番号を知りたい」という問題を考えてみます。
先程の考えを応用すると、先に$ 1,2,4,8,16…2^n回さかのぼったときの頂点の番号を知っていたら、logNで処理ができそうです。
$ 1,2,4,8,16 … 2^n回さかのぼった時の頂点の番号は、
自分から見て8個上のやつから見た8個上のやつは自分から見て16個上
理論を使って、DPテーブルを埋める感じで
まず1を埋めて、その1の結果達を使って2、その結果たちを使って4、その結果たちを使って8を埋めていく…
みたいな感じにして埋めていくとそれぞれの頂点に対してlogN回くらいの計算をすることになるので、テーブル埋めには$ O(NlogN)がかかることになります(知らんけど)。
具体的には、dp[k+1][i] = dp[k][ dp[k][i] ] みたいな感じになりそうです。