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

その他, その他競プロ, 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++ での実装例

練習問題