No.173 カードゲーム(Medium)
No.173 カードゲーム(Medium) - yukicoder
- ARC003 D - シャッフル席替え - shifth’s blogでやったモンテカルロ法の復習問題。というかこの問題を解くために ARC003 を解いたんだけど。
- 等確率を計算したつもりが等確率になっていなくてバグに悩んだ。できるだけシンプルに書くようにしないと...。
class CardGameMedium { public: void solve(void) { int N; double Pa,Pb; cin>>N>>Pa>>Pb; vector<int> A(N); vector<int> B(N); REP(i,N) cin>>A[i]; REP(i,N) cin>>B[i]; std::mt19937 engine; uniform_real_distribution<double> g(0,1); const int T = 200000; // O(T*N^2*log(N)) double p = 0.0; REP(_,T) { int scoreA = 0; int scoreB = 0; auto a(A); auto b(B); REP(i,N) { int ia,ib; ia = ib = 0; if (a.size() > 1) { sort(RANGE(a)); sort(RANGE(b)); double u = g(engine); if ( u >= Pa ) {// 最小値以外のカードを当確率で選ぶ int x = (u-Pa)/(1.0-Pa)*(a.size()-1); ia = x+1; } u = g(engine); if ( u >= Pb ) { int x = (u-Pb)/(1.0-Pb)*(b.size()-1); ib = x+1; } } if (a[ia] > b[ib]) scoreA += a[ia]+b[ib]; else if (a[ia] < b[ib]) scoreB += a[ia]+b[ib]; a.erase(a.begin()+ia); b.erase(b.begin()+ib); } if (scoreA > scoreB) p += 1; } p /= T; cout<<setprecision(20)<<p<<endl; } };