乱択

https://codeforces.com/blog/entry/61587 の必要なところのメモ

乱数生成

rand()

乱数生成の質が微妙なのでやめよう
こどふぉだと最大値が32767しかないのでさらにまずい

mt19937

C++11以上で追加された機能でメルセンヌツイスターで乱数を生成する

• 高速
• 最大値が2³¹-1
• 乱数の質もいい

64bitの乱数がほしいならmt19937_64を使うとできる

乱数のseedが他人にバレるとまずい
chrono::steady_clock::now().time_since_epoch().count()
とか
(uint64_t) new char
とかを使おう

一様乱数の生成

rand() % 1000 → 一様にならないのでだめ
uniform_int_distribution → これを使おう

配列のシャッフル

random_shuffle → 内部でrandを使ってるのでやめよう
shuffle → こっちを使おう

一様乱数を生成するコード

struct dice {
    mt19937 mt;
    dice() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
    // [0, x)の一様乱数
    ll operator()(ll x) { return this->operator()(0, x - 1); }
    // [x, y]の一様乱数
    ll operator()(ll x, ll y) {
        uniform_int_distribution<ll> dist(x, y);
        return dist(mt);
    }
} rnd;

int main() {
    cout << rnd(100) << endl;
    cout << rnd(30, 80) << endl;
}

rand()をどうやって落とす？

https://codeforces.com/blog/entry/61675