Namaran

Code daily. Without assist.

2026-11-07

replay_turn.cpp

#include <cstdint>
#include <random>
#include <utility>

std::pair<std::uint_fast32_t, std::uint_fast32_t> replay_turn(std::uint_fast32_t seed,
                                                              unsigned long long turn) {
}

あるシミュレーションは、シード seed で作った std::minstd_rand0 を1つだけ使い、毎ターン、その呼び出し演算子で値を2つ引いて、先の値を x、後の値を y にします。記録に残っているのはシードだけです。0から数えて turn 番目のターンで引いた x と y を、この順の std::pair で返す replay_turn を書いてください。turn が0なら、エンジンが最初に出す2つの値です。

入力例 1

replay_turn(1, 0)

出力例 1

{16807, 282475249}

入力例 2

replay_turn(1, 1)

出力例 2

{1622650073, 984943658}

入力例 3

replay_turn(42, 0)

出力例 3

{705894, 1126542223}
Reference

Reference

#include <cstdint>
#include <iostream>
#include <random>
#include <utility>

std::pair<std::uint_fast32_t, std::uint_fast32_t> replay_turn(std::uint_fast32_t seed,
                                                              unsigned long long turn) {
    std::minstd_rand0 g(seed);
    g.discard(2 * turn);
    auto x = g();
    auto y = g();
    return {x, y};
}

乱数エンジンが出す列は、シードと、それまでに引いた回数だけで決まります。同じシードで新しいエンジンを作り、元のシミュレーションが turn 番目のターンより前に引いた分だけ進めれば、そのターンを始める直前の状態に戻れます。1ターンで2回引くので、読み飛ばすのは turn 回ではなく 2 * turn 回で、discard がその分だけエンジンを進めます。そこから2回引いた値が、そのターンの x と y です。これは参考実装で、唯一の正解ではありません。discard の代わりに、2 * turn 回 g() を呼んで捨てるループでも同じ結果になります。

std::minstd_rand0 は、前の値に16807を掛けて2147483647で割った余りを次の値にするエンジンで、この計算は規格が決めています。シードが1なら最初の値は16807、次は16807の2乗の282475249です。入力例1はこの2つで、入力例2は2つ読み飛ばしたあとの3つ目と4つ目です。discard(turn) と書くと、入力例2ではターン0の y から引き始めてしまい、{282475249, 1622650073} を返します。規格が計算方法まで決めているのはエンジンだけで、std::uniform_int_distribution などの分布がエンジンの値をどう変換するかは標準ライブラリの実装に任されています。別の環境でも同じ値を再現したいなら、エンジンの出力をそのまま使うか、変換を自分で書きます。