UVa 11500 : Vampires

UVa演習 2014/7/14 (月) 問2

問題リンク : http://uva.onlinejudge.org/external/115/11500.html

問題概要：
2人のプレイヤーでゲームを行う
プレイヤー１の体力はEV1,プレイヤー２の体力はEV2である
ゲームがはじまるとプレイヤーが交互にサイコロをふっていく
サイコロのでた目がAT以下であればプレイヤー１の勝利
それ以外であればプレイヤー２の勝利
勝利したプレイヤーは負けたプレイヤーからDだけ体力を吸収する
つまり、プレイヤー１が勝利した場合
EV1 => EV1 + D
EV2 => EV2 - D
となる
体力が０以下になったプレイヤーがでたらゲームが終わる
プレイヤー１が勝利する確率をもとめよ

解法：
メモ化再帰 or ギャンブラー破産問題の公式を利用
各プレイヤーの体力、その時の確率、深さをもってメモ化再帰をして通った
確率がEPS以下になったら０をリターンするのだが、EPSは1e-270くらいにしないとうまくいかない

ギャンブラー破産問題 : Gambler's ruin - Wikipedia, the free encyclopedia
上の公式に当てはめると簡単に答えがでる
今回体力はDだけ移動するので、各プレイヤーの体力をDで割ること

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-320)
#define equals(a,b) (fabs((a)-(b))<EPS)
using namespace std;

const int MAX_D = 2000;
double memo[30][30][MAX_D];
int AT,D;
double P;


double dfs(int EV1,int EV2,double tmp,int depth){

  if( equals(tmp,0) ) return tmp;

  if( EV1 <= 0 || EV2 <= 0 ) {
    if( EV2 <= 0 ) return tmp;
    return 0;
  }
  //assert( depth < MAX_D );
  if( depth < MAX_D && memo[EV1][EV2][depth] >= 0.0 ) return memo[EV1][EV2][depth];
  double ret  = dfs(EV1+D,EV2-D,tmp*P,depth+1);
  ret += dfs(EV1-D,EV2+D,tmp*(1-P),depth+1);
  if( depth < MAX_D ) memo[EV1][EV2][depth] = ret;
  return ret;
}

/*
 Gambler 1 が勝利する確率
n1 : ギャンブラー１が最初に所持している金額
n2 : ギャンブラー２が最初に所持している金額
p  : ギャンブラー１が勝利する確率
D  : 勝利によって移動する金額
*/
double GamblersRuin(double n1,double n2,double p,double D){
  n1 = ceil(n1/D), n2 = ceil(n2/D);
  double q = 1 - p;
  if( equals(p,0.5) ) return n1 / ( n1 + n2 );
  else return (1.0-pow(q/p,n1))/(double)(1.0-pow(q/p,(int)(n1+n2)));
}

int main(){
  int EV1,EV2;
  while( 1 ){
    scanf("%d %d %d %d",&EV1,&EV2,&AT,&D);
    if( EV1 == 0 && EV2 == 0 && AT == 0 && D == 0 ) break;
    double p = (double) AT / 6.0;
    printf("%.1f\n",GamblersRuin(EV1,EV2,p,D)*100);
    /*
    rep(i,EV1+EV2+1) rep(j,EV1+EV2+1) rep(k,MAX_D) memo[i][j][k] = -1;
    P = (double)AT/6.0; // a probability that Vampire 1 wins a combat
    printf("%.1lf\n",dfs(EV1,EV2,1,0)*100.0);
    */
  }
  return 0;
}