結果

問題 No.173 カードゲーム（Medium）
ユーザー antaanta
提出日時 2015-03-27 00:07:14
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,864 ms / 3,000 ms
コード長 2,559 bytes
コンパイル時間 901 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-11 10:30:20
合計ジャッジ時間 10,751 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
4,384 KB
testcase_01 AC 40 ms
4,384 KB
testcase_02 AC 1,454 ms
4,384 KB
testcase_03 AC 1,452 ms
4,380 KB
testcase_04 AC 1,405 ms
4,380 KB
testcase_05 AC 1,119 ms
4,384 KB
testcase_06 AC 764 ms
4,380 KB
testcase_07 AC 548 ms
4,380 KB
testcase_08 AC 531 ms
4,380 KB
testcase_09 AC 1,864 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

unsigned xor128() {
	static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	unsigned t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

double xor128d() {
	return xor128() * 2.3283064365386963e-10;
}

int main() {
	int N;
	double P[2];
	scanf("%d%lf%lf", &N, &P[0], &P[1]);
	vector<int> A[2];
	rep(k, 2) A[k].resize(N);
	rep(i, N) scanf("%d", &A[0][i]);
	rep(i, N) scanf("%d", &A[1][i]);
	rep(k, 2) sort(all(A[k]));
	int win = 0, Iter = 500000;
	rep(ii, Iter) {
		int a[2] = { (1 << N)-1, (1 << N)-1 };
		int points[2] = { 0, 0 };
		rep(r, N) {
			int card[2] = { -1, -1 };
			rep(k, 2) {
				double Q = P[k];
				int i = a[k];
				int p = N, q = -1;
				rep(j, N) if(i >> j & 1) {
					-- p;
					if(q == -1) q = j;
				}
				if(i == (1 << q)) {
					card[k] = A[k][q];
					a[k] = 0;
				}else {
					double rnd = xor128d();
					if(rnd < Q) {
						card[k] = A[k][q];
						a[k] = i & ~(1 << q);
					}else {
						rnd -= Q;
						double step = (1 - Q) / (N - 1 - p);
						reu(j, q+1, N) if(i >> j & 1) {
							if(rnd < step) {
								card[k] = A[k][j];
								a[k] = i & ~(1 << j);
								break;
							}else {
								rnd -= step;
							}
						}
					}
				}
			}
			points[card[0] > card[1] ? 0 : 1] += card[0] + card[1];
		}
		if(points[0] > points[1])
			++ win;
	}
	printf("%.7f\n", win * 1. / Iter);
	return 0;
}
0