rand(), random_shuffle()は危険だよーというお話

Article

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

代わりに

• mt19937
• shuffle
• を使おうとのこと

random_deviceじゃだめなのか？

• 実装により、出力される乱数が固定される

std::random_deviceに騙された。 実装によっては決定的な値しか返さないのか…https://t.co/32OLNL4YGv

— koyumeishi (@koyumeishi_) 2016年2月19日

• メルセンヌ・ツイスターの方が速い
• 非決定性（再現・デバッグしづらい）

mt使おう

• 使用例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define p(s) cout<<(s)<<endl
#define pn(s) cout << (#s) << " " << (s) << endl

void vprint(vector<ll> A){
    ll L = A.size();
    FOR(i, 0, L){
        if(i) cout << ' ';
        cout << A[i];
    }
    cout << endl;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N = 10;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<ll> permutation(N);

    for (ll i = 0; i < N; i++)
        permutation[i] = i;

    shuffle(permutation.begin(), permutation.end(), rng);  
    vprint(permutation);  

    pn(rng());
    pn(rng());
    pn(rng());
    pn(rng());
    pn(rng());

    return 0;
}

• output

3 9 1 6 7 4 2 0 5 8
rng() 2994179312
rng() 1236679741
rng() 775246944
rng() 2937776244
rng() 1755752338