yukicoder No.133 - カードゲーム

Source

ニコニコミュニティ
問題文

問題概要

$2$ 人でカードゲームをする.
$1$ から $2N$ までが書かれた $2N$ 枚のカードがあり,$2$ 人にそれぞれ $N$ 枚ずつ配る.
それぞれのプレイヤーは $N$ 回だけ,配られたカードを順番に出す.
毎回出されたカードを比較して,数が大きいほうが勝ち.
勝った回数が多いほうが,ゲーム全体の勝者となる.
ただし,勝った回数が等しいなら引き分けで,全てのカードはちょうど $1$ 回出す.
プレイヤー $1,2$ に配られたカードが与えられるので,そのゲームでプレイヤー $1$ が勝つ確率を求める問題.
ただし,各プレイヤーは,毎回残されたカードからランダムに出すカードを選ぶ.

解法

プレイヤー $2$ が出すカードそれぞれについて,対応するプレイヤー $1$ が出すカードのパターンを $N!$ 通り全て試せば良い.
時間計算量 $O(N!)$.
ちなみに,要求誤差が緩いのでモンテカルロ法でも通る.

C++によるスパゲッティなソースコード

#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: 2017年07月24日15時50分55秒
Last modified: 2015年01月29日00時12分48秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: