yukicoder No.173 カードゲーム（Medium）

問題

問題概要

省略

解法

誤差の許容が大きいため、モンテカルロ法を使えばいいらしい。やっていることは、確率pで1枚目を選ぶとあるので、乱数で0~1までだし、pより小さければ1枚目を選び、そうでなければ、その他のものを等しい確率で選ぶというシミュレーションを何度も行っている。誤差が緩い場合、何回もやれば、正確な値に近づくという考えでやっていってもいいらしい。

ミス

こういう感じの問題は初めて。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int n;
double pa, pb;

vector<int> solve(double p){//取り出す順番の添字を返す
    vector<int> v, ret;
    rep(i, n) v.push_back(i);//スロット

    int x;
    rep(i, n - 1){
        //rand()%(B-A+1)+A; B=1000 A=0
        double nowp = rand() % (1001) / 1000.0;//乱数で0.000~1.000
        if(nowp <= p) x = 0;//0番目を選択
        else x = 1 + (n - i - 1) * (nowp - p) / (1 - p);//その他のものを等しい確率で選ぶ
        if(x < 0) x = 0;
        if(n - 1 - i < x) x = n - 1 - i;
        ret.push_back(v[x]);
        v.erase(v.begin() + x);
    }
    ret.push_back(v[0]);//使うカードが一枚しかない場合
    return ret;
}

int main(void){
    cin >> n >> pa >> pb;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    int win = 0;
    rep(i, 400000){
        vector<int> va, vb;
        va = solve(pa);
        vb = solve(pb);
        int sa = 0, sb = 0;
        rep(j, n){
            if(a[va[j]] > b[vb[j]]) sa += a[va[j]] + b[vb[j]];
            else sb += a[va[j]] + b[vb[j]];
        }
        if(sa > sb) win++;
    }
    printf("%.9f\n", (double)win / 400000.0);
    return 0;
}