ダブリングの基本概念とその応用

2020年5月11日2020年11月29日その他,その他競プロ,LCA,ダブリング,繰り返し二乗法

ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において

• 前処理：\(O(N \log K)\) 時間, \(O(N \log K)\) 空間
• クエリ：\(O(\log K)\)

で行うことができるようにするアルゴリズムです。

繰り返し二乗法もダブリングの一種と捉えることができ、最近共通祖先(LCA)の計算にも利用されます。

アルゴリズム

※前処理では以下のような計算をします。

• それぞれの要素について 1 個先の要素が何か記録
• 前の結果を利用して、それぞれの要素について 2 個先の要素が何か記録
• 前の結果を利用して、それぞれの要素について 4 個先の要素が何か記録
• 前の結果を利用して、それぞれの要素について 8 個先の要素が何か記録
• 前の結果を利用して、それぞれの要素について 16 個先の要素が何か記録
• …

\(2^k\) 先の要素が分かっていれば「 “\(2^k\) 先の要素" の\(2^k\) 先」を簡単に求めることができるので、「\(2^{k+1}\) 先の要素が何か」を高速に求めることができます。

※クエリでは、前処理した結果を利用しています。繰り返し二乗法について見るとイメージしやすいと思います。

計算量

K個先の要素を求めたい時の計算量は以下のようになります。

• 前処理：\(O(N \log K)\) 時間, \(O(N \log K)\) 空間
• クエリ：\(O(\log K)\)

問題例: ABC167 D – Teleporter

町が \(N\) 個ある。町 \(i\) から町 \(A_i\) に移動することを K 回繰り返す。
町 1 から始めた時、最終的にどの町にたどり着くか？

制約

• \(2 \leq N \leq 2 \times 10^5\)
• \(1 \leq A_i \leq N\)
• \(1 \leq K \leq 10^{18}\)

考え方

単純にシミュレーションすると、O(K) の計算量になって間に合いません。

そこで、ダブリングの考え方が使えます。

• doubling[k][i] : 町 \(i\) から \(2^k\) 先の町はどこか？

という情報を前計算することで、

• 前処理：\(O(N \log K)\) 時間, \(O(N \log K)\) 空間
• クエリ：\(O(\log K)\)

計算することができます。

他にも、周期性を利用した解法などもあります。詳しくは D – Teleporter 解説 (AtCoder Beginner Contest 167) を見て下さい。

C++ での実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        A[i]--;  // 0-indexed に変更
    }
    int logK = 1;
    while ((1LL << logK) <= K) logK++;
    // doubling[k][i] : i番目から 2^k 進んだ町
    vector<vector<int> > doubling(logK, vector<int>(N));
    for (int i = 0; i < N; i++) {
        doubling[0][i] = A[i];
    }
    // 前処理 doubling の計算
    for (int k = 0; k < logK - 1; k++) {
        for (int i = 0; i < N; i++) {
            doubling[k + 1][i] = doubling[k][doubling[k][i]];
        }
    }
    int now = 0;
    for (int k = 0; K > 0; k++) {
        if (K & 1) now = doubling[k][now];
        K = K >> 1;
    }
    cout << now + 1 << endl;
}

練習問題

• AtCoder Beginner Contest 167 D – Teleporter (解説)
• [AOJ] NTL_1 Power : 繰り返し二乗法
• AOJ GRL_5_C Lowest Common Ancestor : LCA