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

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

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

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

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

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

アルゴリズム

ダブリングによるK個先の要素の求め方:

  • 前処理:「doubling[k][i] : \(i\) 番目の要素から \(2^k\) 先の要素は何か」を以下の式を利用して計算
    • doubling[k+1][i] = doubling[k][doubling[k][i]]
  • クエリ:前処理した結果を利用して K 個先の要素を求める
    • 現在地を now として、\(K\) を2進数として見た時の全ての桁について以下を行う
      • \(K\) の \(k\) 桁目 が 1 ならば now = doubling[k][now] とする

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

  • それぞれの要素について 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;
}

練習問題