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

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

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

前処理：O(NlogK) 時間, O(NlogK) 空間
クエリ：O(logK)

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

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

Contents

1. アルゴリズム
- 1.1. 計算量
2. 問題例: ABC167 D – Teleporter
3. 練習問題

アルゴリズム

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

前処理：「doubling[k][i] : i 番目の要素から 2k 先の要素は何か」を以下の式を利用して計算
- 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 個先の要素が何か記録
…

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

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

計算量

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

前処理：O(NlogK) 時間, O(NlogK) 空間
クエリ：O(logK)

問題例: ABC167 D – Teleporter

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

制約

2≤N≤2×105
1≤Ai≤N
1≤K≤1018

考え方

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

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

doubling[k][i] : 町 i から 2k 先の町はどこか？

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

前処理：O(NlogK) 時間, O(NlogK) 空間
クエリ：O(logK)

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

他にも、周期性を利用した解法などもあります。詳しくは 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;
}

#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

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

ディスカッション

コメント一覧

まだ、コメントがありません