保存されている過去のバージョンの一覧

2015年01月28日23時23分19秒

dwangoプログラミングコンテスト予選 C問題 - ゲーマーじゃんけん

Source

dwangoプログラミングコンテスト予選
問題文

問題概要

$N$ 人の人から $1$ 人の勝者をゲーマーじゃんけんにより決めるとき，必要なラウンド数の期待値を求める問題．
ただし，ゲーマーじゃんけんのルールは以下の通り．
各ラウンドでは，まだ勝ち残っている人がグー，チョキ，パーのどれかの手を出す．
全員が同じ手，または，$3$ 種類すべての手が同じ人数だけ出されている場合は，あいことなり，全員が勝ち残る．
出した人がいる手の中で，最も少ない人数が出した手が一意に定まるなら，その手を出した人のみが勝者になる．
そうでなければ，最も少ない人数が出した手が $2$ 種類あるので，その $2$ 種類のうち，通常のじゃんけんで強い手を出した人のみが勝者になる．
勝ち残る人が $1$ 人になった時点で終了する．

解法

動的計画法により求める．
$k$ 人が残っている時の必要なラウンド数の期待値を $k$ が小さい方から求めていく．
その際，それぞれグー，チョキ，パーを出した人数を総当りして，次のラウンドが何人になる確率がいくらというのを全て求める．
あいこになると減らないことがあるので，あいこになる確率を $p$，求めたい期待値を $x$ として，$x = a + p (x+1)$ という式が得られるので，$x = (a+p)/(1-p)$ などと式変形して求める．
もしくは，ターン数は大きくなる確率は非常に小さいので，ターン数も状態に入れて，$100$ ターン程度まで考えてあげたり，連立一次方程式に帰着して，ガウスザイデルやガウスジョルダンなどしても良い．
時間計算量は $O(N^3)$ 程度．

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;
double dp[120];
double C[120][120];
double pw[120];

double prob(int x, int y, int z){
  int s = x + y + z;
  return pw[s] * C[s][x] * C[s-x][y];
}

int main(){
  int i, j, k;
  int x, y, z, nx;
  int arr[3];
  double p, dame;

  rep(i,120) C[0][i] = 0;
  rep(i,120) C[i][0] = 1;
  REP(i,1,120) REP(j,1,120) C[i][j] = C[i-1][j-1] + C[i-1][j];

  pw[0] = 1;
  REP(i,1,120) pw[i] = pw[i-1] / 3;

  dp[0] = dp[1] = 0;
  REP(i,2,101){
    dp[i] = 0;
    dame = 0;
    rep(x,i+1) rep(y,i+1){
      z = i - x - y;
      if(z < 0) continue;

      p = prob(x, y, z);
      arr[0] = x;
      arr[1] = y;
      arr[2] = z;
      sort(arr, arr+3);
      if(arr[0]==arr[2]){ dame += p; continue; }
      if(arr[0]==0 && arr[1]==0){ dame += p; continue; }
      nx = arr[0];
      if(nx==0) nx = arr[1];
      dp[i] += (dp[nx] + 1) * p;
    }
    dp[i] = (dp[i] + dame) / (1 - dame);
  }

  reader(&N);
  writerLn(dp[N]);

  return 0;
}

Current time: 2024年04月19日18時25分53秒
Last modified: 2015年01月28日23時23分19秒 (by laycrs)
Tags: Competitive_Programming AtCoder dwango2015-prelims
トップページに戻る

Logged in as: unknown user (not login)

ログイン：