ウツギ博士にポケモンの進化について熱く語ってもらう.

AbuseDrUtsugi.cpp

#include <iostream>
#include <iomanip>

using namespace std;

// 次の乱数を取得
uint32_t next(uint32_t s) {
    return 0x41C64E6D * s + 0x00006073;
}

// 前の乱数を取得
// 注:
// S[n+1] = (0x41C64E6D * S[n] + 0x6073) % 0x100000000
// に対して
// S[n-1] = (0xEEB9EB65 * S[n] + 0x0A3561A1) % 0x100000000
// が成り立つことを利用
uint32_t prev(uint32_t s) {
    return 0xEEB9EB65 * s + 0x0A3561A1;
}

// 実乱数を取得
uint16_t r(uint32_t s) {
    return s >> 16;
}

// 15連続で``r[n] % 3``が``0``になれば真
bool is_15_chain(uint32_t s_n) {
    uint32_t s = s_n;
    for (int i = 0; i < 15; i++) {
        if (r(s) % 3 != 0) {
            return false;
        }
        s = next(s);
    }
    return true;
}

// 800F~3000Fで実現可能な初期Seedであれば真
bool is_feasible_initial_seed(uint32_t s_0) {
    int first_frame = 800;
    int last_frame  = 3000;

    // initial seed: 0xABCDEFGH
    int min_AB   = 1 * 1 + 0 + 10;
    int max_AB   = 12 * 31 + 59 + 59;
    int min_CD   = 0;
    int max_CD   = 23;
    int min_EFGH = first_frame;
    int max_EFGH = last_frame + 2099 - 2000;

    int AB   = s_0 >> 24;
    int CD   = (s_0 >> 16) % 0x100;
    int EFGH = s_0 % 0x10000;

    // 実現不可能な初期Seedを除外
    if (
        AB < min_AB || AB > max_AB
        || CD < min_CD || CD > max_CD
        || EFGH < min_EFGH || EFGH > max_EFGH
    ) {
        return false;
    }
    return true;
}

int main(void) {
    cout << setw(3) << "n";
    cout << setw(12) << "S[n]";
    cout << setw(12) << "S[0]" << endl;

    int min_consumption = 3;  // 最小消費数
    int max_consumption = 10; // 最大消費数

    // ``S[n]``を総当り
    for (uint64_t s_n = 0; s_n < 0x100000000; s_n++) {
        // 15連続で``r[n] % 3``が``0``にならなければ候補から除外
        if (!is_15_chain(s_n)) continue;

        uint32_t s = s_n;
        int n = 0;

        // 徘徊ポケモンによる消費数分だけスキップ
        for (int i = 0; i < min_consumption; i++) {
            s = prev(s);
            n++;
        }

        // 初期Seed候補の検索
        for (int i = min_consumption; i <= max_consumption; i++) {
            s = prev(s);
            n++;

            // 実現可能な初期Seedがあれば出力
            if (is_feasible_initial_seed(s)) {
                cout << setw(3) << dec << noshowbase << n;
                cout << setw(12) << hex << uppercase << showbase << s_n;
                cout << setw(12) << hex << uppercase << showbase << s << endl;
            }
        }
        
    }
    return 0;
}