結果

問題 No.173 カードゲーム（Medium）
コンテスト
ユーザー moti
提出日時 2015-04-03 10:40:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 655 ms / 3,000 ms
コード長 1,050 bytes
コンパイル時間 1,354 ms
コンパイル使用メモリ 163,948 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-04 01:36:53
合計ジャッジ時間 6,091 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

int N, T;
double pa,pb;
int A[22], B[22];
int win, sum;

vector<int> getrandvec(double p,
		default_random_engine& gene,
		uniform_real_distribution<double>& dist) {
	int x;
	vector<int> v,r;
	rep(i, N) {
		v.push_back(i);
	}

	rep(i, N-1) {
		double d = dist(gene);
		if(d < p) x = 0;
		else x = 1+(N-1-i)*(d-p) / (1-p);

		r.push_back(v[x]);
		v.erase(v.begin()+x);
	}
	r.push_back(v[0]);
	return r;
}

int main() {

	cin >> N;
	double pa, pb; cin>>pa>>pb;
	rep(i, N) cin >> A[i], T += A[i];
	rep(i, N) cin >> B[i], T += B[i];

	sort(A, A+N);
	sort(B, B+N);

	default_random_engine gene;
	uniform_real_distribution<double> dist(0.,1.);

	int x;

	rep(i, 300000) {
		sum ++;
		vector<int> va, vb;
		va = getrandvec(pa, gene, dist);
		vb = getrandvec(pb, gene, dist);
		x = 0;
		rep(y, N) if(A[va[y]] > B[vb[y]]) {
			x += A[va[y]] + B[vb[y]];
		}
		if(x > T/2) { win ++; }
	}

	printf("%.10f\n", (double)win/sum);

	return 0;
}
0