test/unittest/tadpole-array.test.cpp

• View this file on GitHub
• Last update: 2026-10-13 06:02:01+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• おたまじゃくし配列 (src/data_structures/tadpole-array.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// TadpoleArray を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <iostream>
#include <random>
#include <vector>

#include "../../src/data_structures/tadpole-array.hpp"

int main() {
    std::mt19937_64 rng(314);
    bool ok = true;
    for (int rep = 0; rep < 2000 && ok; rep++) {
        int n = rng() % 6 + 1;
        int k = rng() % n;  // 最後の次は k 番目に戻る
        std::vector<int> v(n);
        for (int& x : v) x = rng() % 100;
        TadpoleArray<int> ta(v, k);

        // 愚直: 0 から順に進み、末尾の次は k に戻る
        int p = 0;
        for (size_t i = 0; i < 200; i++) {
            if (ta.at(i) != v[p] || ta[i] != v[p]) ok = false;
            p = (p + 1 < n) ? p + 1 : k;
        }
        // 大きな添字: ループ部分の長さ n - k ごとに同じ値になる
        for (int t = 0; t < 20; t++) {
            size_t i = k + rng() % 1000000000000ULL;
            size_t period = n - k;
            if (ta[i] != ta[k + (i - k) % period]) ok = false;
            if (ta[i] != ta[i + period * (rng() % 1000)]) ok = false;
        }
        // コピーしても同じ列を表す
        TadpoleArray<int> copy(ta);
        for (size_t i = 0; i < 50; i++) {
            if (copy[i] != ta[i]) ok = false;
        }
    }
    if (ok) std::cout << "Hello World" << std::endl;
    else std::cerr << "failed" << std::endl;
}

#line 1 "test/unittest/tadpole-array.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// TadpoleArray を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <iostream>
#include <random>
#include <vector>

#line 2 "src/data_structures/tadpole-array.hpp"

/**
 * @file tadpole-array.hpp
 * @brief おたまじゃくし配列
 */

#include <cassert>
#line 10 "src/data_structures/tadpole-array.hpp"
/**
 * @brief おたまじゃくし配列
 * 特定の位置でループする構造
 * @tparam T
 */
template <typename T>
struct TadpoleArray {
   private:
    std::vector<T> data;
    size_t k;

   public:
    /**
     * @brief 最後の次のインデックスがi
     */
    TadpoleArray(const std::vector<T>& v, int i) : data(v) {
        assert(0 <= i and i < static_cast<int>(data.size()));
        k = static_cast<size_t>(i);
    }
    TadpoleArray() = default;
    TadpoleArray(const TadpoleArray&) = default;
    T at(size_t i) const {
        if (i < k) return data[i];
        return data[(i - k) % (data.size() - k) + k];
    }
    T operator[](size_t i) const {
        return at(i);
    }
};
#line 11 "test/unittest/tadpole-array.test.cpp"

int main() {
    std::mt19937_64 rng(314);
    bool ok = true;
    for (int rep = 0; rep < 2000 && ok; rep++) {
        int n = rng() % 6 + 1;
        int k = rng() % n;  // 最後の次は k 番目に戻る
        std::vector<int> v(n);
        for (int& x : v) x = rng() % 100;
        TadpoleArray<int> ta(v, k);

        // 愚直: 0 から順に進み、末尾の次は k に戻る
        int p = 0;
        for (size_t i = 0; i < 200; i++) {
            if (ta.at(i) != v[p] || ta[i] != v[p]) ok = false;
            p = (p + 1 < n) ? p + 1 : k;
        }
        // 大きな添字: ループ部分の長さ n - k ごとに同じ値になる
        for (int t = 0; t < 20; t++) {
            size_t i = k + rng() % 1000000000000ULL;
            size_t period = n - k;
            if (ta[i] != ta[k + (i - k) % period]) ok = false;
            if (ta[i] != ta[i + period * (rng() % 1000)]) ok = false;
        }
        // コピーしても同じ列を表す
        TadpoleArray<int> copy(ta);
        for (size_t i = 0; i < 50; i++) {
            if (copy[i] != ta[i]) ok = false;
        }
    }
    if (ok) std::cout << "Hello World" << std::endl;
    else std::cerr << "failed" << std::endl;
}

Back to top page