$2$ 人でカードゲームをする.
$1$ から $2N$ までが書かれた $2N$ 枚のカードがあり,$2$ 人にそれぞれ $N$ 枚ずつ配る.
それぞれのプレイヤーは $N$ 回だけ,配られたカードを順番に出す.
毎回出されたカードを比較して,数が大きいほうが勝ち.
勝った回数が多いほうが,ゲーム全体の勝者となる.
ただし,勝った回数が等しいなら引き分けで,全てのカードはちょうど $1$ 回出す.
プレイヤー $1,2$ に配られたカードが与えられるので,そのゲームでプレイヤー $1$ が勝つ確率を求める問題.
ただし,各プレイヤーは,毎回残されたカードからランダムに出すカードを選ぶ.
プレイヤー $2$ が出すカードそれぞれについて,対応するプレイヤー $1$ が出すカードのパターンを $N!$ 通り全て試せば良い.
時間計算量 $O(N!)$.
ちなみに,要求誤差が緩いのでモンテカルロ法でも通る.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
int N;
int A[10], B[10];
int main(){
int i, j, k;
int win=0, all=0;
int a, b;
int ind[10];
reader(&N);
rep(i,N) reader(A+i);
rep(i,N) reader(B+i);
rep(i,N) ind[i] = i;
do{
a = 0;
rep(i,N){
if(A[ind[i]] > B[i]) a++;
if(A[ind[i]] < B[i]) a--;
}
if(a > 0) win++;
all++;
}while(next_permutation(ind,ind+N));
writerLn((double)win/all);
return 0;
}
Current time: 2024年04月25日08時52分28秒
Last modified: 2015年01月29日00時12分48秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る
Logged in as: unknown user (not login)