hotaruの蛍雪日記

競プロとゲームをしています

ダブリングを実装した

ダブリングを実装した。 ダブリングをクラス化したかったが、抽象化が足りないのかクラスを改造しないと解けない問題が出てしまった。

ダブリングについては先のリンクを読んでください。 https://atcoder.jp/contests/abc167/tasks/abc167_d

D - Teleporter - ABC167D

問題へのリンク

クラスのソースコードを貼るついでに私が実装したダブリングクラスでTeleporterを解いたソースコードを貼る。 Teleporterはダブリングの初歩的な問題。

#include <iostream>
#include <vector>
using namespace std;

// ダブリング
// ダブリングについては https://algo-logic.info/doubling/ を参照
class doubling {
   private:
    // next[j][i]: i番目の要素のj個先の要素
    vector<vector<long long>> next;

   public:
    // コンストラクタ
    // ダブリングの前処理をする
    // maxk: 最大のK
    // next1: i番目の要素から1個先の要素のvector
    doubling(long long maxk, vector<long long> &next1) {
        // nextを初期化 リサイズしてnext[0]を初期化。
        const long long log2k = log2K(maxk);
        next.resize(log2k);
        next.front() = next1;
        const long long n = next1.size();
        for (auto &&next_i : next) {
            next_i.resize(n);
        }

        // ダブリングの前処理
        for (long long i = 0; i < log2k - 1; i++) {
            for (long long j = 0; j < n; j++) {
                next[i + 1][j] = next[i][next[i][j]];
            }
        }
    }

    // ダブリングのクエリに答える
    // p番目の要素からk個先の要素を返す
    long long get(long long p, long long k) {
        const long long log2k = log2K(k);
        for (long long i = 0; i < log2k; i++) {
            if (k & (1LL << i)) p = next[i][p];
        }
        return p;
    }
    constexpr long long log2K(long long k) {
        long long log2k = 1;
        while ((1LL << log2k) < k) log2k++;
        return log2k;
    }
};

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    // 入力受け取り
    long long n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (long long i = 0; i < n; i++) cin >> a[i];
    // Aを0-basedに変換
    for (auto &&i : a) {
        i--;
    }

    // ダブリング前処理
    doubling d(k, a);
    // ダブリングクエリ
    const long long ans = d.get(0, k) + 1;

    cout << ans << "\n";
}

コンストラクタにi番目の要素から1個先の要素を渡して前処理する。 メンバ関数でクエリに答える。 クエリが複数飛んでくることを想定して、前処理のKとクエリのKを別にできるようにした。

E - Sequence Sum - ABC179E

問題へのリンク

ある要素からN個先の要素の和を答えろという問題。 想定回はO(M)で周期性を見つけるのだが、ダブリングO(M\log_2N)でも解くことができる。

#include <iostream>
#include <vector>
using namespace std;

// ダブリング
// ダブリングについては https://algo-logic.info/doubling/ を参照
class doubling {
   private:
    // next[j][i]: i番目の要素のj個先の要素
    vector<vector<long long>> next;
    // sums[j][i]: i番目の要素の1個先からj個先の要素までの和
    vector<vector<long long>> sums;

   public:
    // コンストラクタ
    // ダブリングの前処理をする
    // maxk: 最大のK
    // next1: i番目の要素から1個先の要素のvector
    doubling(long long maxk, vector<long long> &next1) {
        // nextを初期化 リサイズしてnext[0]を初期化。
        const long long log2k = log2K(maxk);
        next.resize(log2k);
        next.front() = next1;
        const long long n = next1.size();
        for (auto &&next_i : next) {
            next_i.resize(n);
        }

        sums.resize(log2k);
        sums.front() = next1;
        for (auto &&sums_i : sums) {
            sums_i.resize(n);
        }

        // ダブリングの前処理
        for (long long i = 0; i < log2k - 1; i++) {
            for (long long j = 0; j < n; j++) {
                next[i + 1][j] = next[i][next[i][j]];
                sums[i + 1][j] = sums[i][j] + sums[i][next[i][j]];
            }
        }
    }

    // ダブリングのクエリに答える
    // p番目の要素からk個先の要素を返す
    long long get(long long p, long long k) {
        long long sum = 0;
        const long long log2k = log2K(k);
        for (long long i = 0; i < log2k; i++) {
            if (k & (1LL << i)) {
                sum += sums[i][p];
                p = next[i][p];
            }
        }
        return sum;
    }
    constexpr long long log2K(long long k) {
        long long log2k = 1;
        while ((1LL << log2k) < k) log2k++;
        return log2k;
    }
};

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    // 入力受け取り
    long long n, x, m;
    cin >> n >> x >> m;
    // b[i]: i番目の要素の1つ先の要素
    vector<long long> b(m);
    for (int i = 0; i < m; i++) {
        b[i] = ((long long)i * i) % m;
    }

    // ダブリング前処理
    doubling d(n, b);
    // ダブリングクエリ
    const long long ans = x + d.get(x, n - 1);

    cout << ans << "\n";
}

クラスを改造して、ダブリングの前処理をしながら1個先から2^i個先までの要素の和を計算するようにした。

  • next[i][j]: j番目の要素から 2^i 先の要素
  • sums[i][j]: j番目の要素の1個先の要素から 2^i 先の要素までの和

次の式が成り立つ。

sums[i + 1][j] = sums[i][j] + sums[i][next[i][j]];

この式を利用してsumsを計算する。

このソースコード競技プログラミング目的なら自由に使用しても構いません。