perogram

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

Article

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

代わりに

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

random_deviceじゃだめなのか?

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

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