ダブリングの使い所さん - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

いろいろな応用が利く、Atcoder700以上らへんでちょくちょく見るダブリングという手法を書く。

概要

まず初めに、ダブリングを応用できそうなシチュエーションについて書く。

ある要素から見て、次の要素は簡単に短時間で求められるが、K個あとの要素は、O(n)かかったりして、簡単に短時間でも止まらない。

この時、ダブリングという手法を利用すると、全体の大きさをMとすると
前計算O(M log M) + クエリごとに、N個先を見るとしてO(log N)
で押さえられる。

詳しいダブリングの解説は、http://satanic0258.hatenablog.com/entry/2017/02/23/222647

satanicさんのブログ参照。

ダブリングのテンプレとしては

const int jlimit = (int)(log2(100000)) + 1;
 
int dp[100000][limitj];//dp[i][j] := i個目のモノから2^j個先のモノの番号
 
for(int i = 0; i < M; i++){
    dp[i][0] = ???;//j == 0についての初期化
}
 
for(int j = 1; j < limitj; j++){
    for(int i = 0; i <= M; i++){
        //i個目のモノから2^j個先のモノは、「i個目のモノから2^(j - 1)個先のモノ」からの「2^(j - 1)個先のモノ」
        //ex  3個目のモノから4個先のモノは、「3個目のモノから 2 個先のモノ」からの「2個先のモノ」
        //式はつぎのように書くといい。
        dp[i][j] = dp[dp[i][j - 1][j - 1];
    }
}
 
//クエリを求めると次のようにする。
 
int l, N;//lからN個先
 
for(int j = limitj - 1; j >= 0; j--){
    if ((1 << j) <= N){
        N -= (1 << j);
        l = dp[l][j];
    }
}
 
 

例　ARC060 E(700)　https://atcoder.jp/contests/arc060/tasks/arc060_c

それぞれのホテルのすぐ次は、二分探索やしゃくとりで簡単に求めることができる。しかし、N個先となればO(N)かけて走査しないとできない。

これは上の条件と全く持って一致してるのでそのまま適用できる。