結果

問題 No.173 カードゲーム(Medium)
ユーザー motimoti
提出日時 2015-04-03 10:40:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 649 ms / 3,000 ms
コード長 1,050 bytes
コンパイル時間 1,239 ms
コンパイル使用メモリ 150,628 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-17 03:57:49
合計ジャッジ時間 5,986 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
4,376 KB
testcase_01 AC 133 ms
4,380 KB
testcase_02 AC 544 ms
4,376 KB
testcase_03 AC 543 ms
4,380 KB
testcase_04 AC 530 ms
4,380 KB
testcase_05 AC 470 ms
4,380 KB
testcase_06 AC 406 ms
4,376 KB
testcase_07 AC 380 ms
4,376 KB
testcase_08 AC 374 ms
4,380 KB
testcase_09 AC 649 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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