ダブリングの簡易的なテスト
(test/datastructure/doubling.test.cpp)

• View this file on GitHub
• Last update: 2021-07-18 14:38:47+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• ダブリング (datastructure/doubling.hpp)

Code

// @title ダブリングの簡易的なテスト
// dummy problem
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include "../../datastructure/doubling.hpp"
using namespace std;

void test_get() {
    vector<int> next = {2,3,1,0};
    Doubling doubling(next);
    // 愚直解と一致することの確認
    vector<int> expected = next;
    for (int q = 1; q < 10000; ++q) { 
        for (int i = 0; i < next.size(); ++i) {
            assert(doubling.get(i,q) == expected[i]);
            expected[i] = next[expected[i]];
        }
    }
}

int main() {
    test_get();

    // dummy output
    cout << "Hello World" << endl;
}

#line 1 "test/datastructure/doubling.test.cpp"
// @title ダブリングの簡易的なテスト
// dummy problem
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#line 1 "datastructure/doubling.hpp"


/**
 * @title ダブリング
 * @brief 要素数Mのある要素に対するN個先の要素取得を前処理 $O(M\log N)$、取得$O(\log N)$で行う
 * @see http://satanic0258.hatenablog.com/entry/2017/02/23/222647
 * @see https://atcoder.jp/contests/typical90/submissions/24345528
 */
#include <vector>

struct Doubling {
    int N; // 要素数 
    // 辿る深さの最大値。最大でQ個先まで見る場合`2^K > Q`を満たすようにKを決める
    // Qがlong longの範囲であれば、K = 63とする
    // FIXME: K >= 64だと、getの(q>>k)がoverflowして取得する値がおかしくなる
    int K;
    const int EMPTY;
    // table[k][i]でi番目の要素の「2^k個先の要素」を指す
    // i番目の要素に対して「2^k個先の要素」が存在しないときは
    // `table[k][i] = EMPTY` となる
    std::vector<std::vector<int>> table;

    Doubling(const std::vector<int>& next, int k): N(next.size()), K(k), EMPTY(-1) {
        init(next);
    }
    Doubling(const std::vector<int>& next): N(next.size()), K(63), EMPTY(-1) {
        init(next);
    }

    void init(const std::vector<int>& next) {
        table.push_back(next);
        for (int k = 0; k < K; ++k) { 
            table.push_back(std::vector<int>(N));
            for (int i = 0; i < N; ++i) {
                if (table[k][i] == EMPTY) {
                    // 2^k個先に要素が無い場合2^(k+1)個先にも要素は無い
                    table[k+1][i] = EMPTY;
                }
                else {
                    // 「2^k個先の要素」の2^k個先の要素は2^(k+1)個先の要素
                    table[k+1][i] = table[k][table[k][i]];
                }
            }
        }

    }

    // p番目の要素のq個先の要素
    // NOTE: 大きい数で答えが合わなかったら、overflowを疑う
    int get(int p, unsigned long long q) const {
        for (int k = K-1; k >= 0; --k) {
            if (p == EMPTY) break;
            if ((q >> k) & 1ULL) {
                // k番目のビットが立っていたらpの位置を2^k先にする
                p = table[k][p];
            }
        }
        return p;
    }
};


#line 7 "test/datastructure/doubling.test.cpp"
using namespace std;

void test_get() {
    vector<int> next = {2,3,1,0};
    Doubling doubling(next);
    // 愚直解と一致することの確認
    vector<int> expected = next;
    for (int q = 1; q < 10000; ++q) { 
        for (int i = 0; i < next.size(); ++i) {
            assert(doubling.get(i,q) == expected[i]);
            expected[i] = next[expected[i]];
        }
    }
}

int main() {
    test_get();

    // dummy output
    cout << "Hello World" << endl;
}

Back to top page