The 2011 Southwestern Europe Regional Contest E, UVa-12391 : Game, Set and Match

問題概要

テニスで、ポイントをとる確率pが与えられる。gameに勝つ確率、setに勝つ確率、matchに勝つ確率をそれぞれ求める問題。

考えたこと

問題文長いけどどうやら一般的なテニスのルールが書いてあるだけらしい。
なのでWikipediaで調べる。
デュースとかタイブレークさえなければ普通の組み合わせで求まる。
でもどうせデュースになった後勝つ確率とかは一次方程式で出るだろう。
実際すぐに計算できた。後はただ実装するだけなんだけど、大した量にならないのでループじゃなくてコピペで頑張ろう。
サンプル通った。投げるとWA。
誤差？念のため桁数をサンプルに合わせたりEPS足したりして再送するもやはりWA。
まだ誤差とれてない？誤差以外のミスは見つけられないのでひたすら誤差を減らす作業をする。
まず足し算は小さい順に足す。nanが出てこないように確率がある程度0や1に近づくと打ちきる。long doubleに書き直す。powを自作のものにする。などをしたけど未だにWA。
0に近いところだと色々まずそうなので、p<0.5のときは余事象の確率を考えるようにした。これでやっとAC。
コンテスト終了後リジャッジされていた。やはり最初に提出したので既に通っていたらしい。

修正したコード

本番出したのは誤差回避のために色々やった結果汚くなって悲しい。

#include <cstdio>
#include <cmath>
using namespace std;

const int MAX_N = 20;
const double EPS = 1e-7;

double point_prob;

int comb[MAX_N][MAX_N];

double solve1(double p, int duce_start = 3){
	if(p > 1.0 - EPS){
		return 1.0;
	}
	if(p < EPS){
		return 0.0;
	}

	double ans = 0.0;

	//デュースなしで勝ち
	for(int lose=0; lose<duce_start; lose++){
		ans += comb[duce_start + lose][lose] * pow(p, duce_start+1) * pow(1.0 - p, lose);
	}

	//デュースから勝ち
	double duce_win = p*p/(1 - 2*p*(1.0-p));
	ans += comb[2*duce_start][duce_start] * pow(p, duce_start) * pow(1.0 - p, duce_start) * duce_win;

	return ans;
}

double solve2(double p, double q){
	if(p > 1.0 - EPS){
		return 1.0;
	}
	if(p < EPS){
		return 0.0;
	}

	double ans = 0.0;

	//6勝で勝ち
	const int tie = 5;
	for(int lose=0; lose<tie; lose++){
		ans += comb[tie+lose][lose] * pow(p, tie+1) * pow(1.0 - p, lose);
	}

	//5勝5敗になる確率
	double p_tie = comb[2*tie][tie] * pow(p, tie) * pow(1.0 - p, tie);

	//7勝5敗で勝ち
	ans += p_tie * p * p;

	//タイブレークから勝ち
	ans += p_tie * 2 * p * (1.0 - p) * solve1(q, 6);

	return ans;
}

double solve3(double p){
	return p*p + 2*(1-p)*p*p;
}

void solve(){
	double game_prob = solve1(point_prob);
	double set_prob = solve2(game_prob, point_prob);
	double match_prob = solve3(set_prob);
	printf("%.11f %.11f %.11f\n", game_prob, set_prob, match_prob);
}

int main(){

	for(int n=0; n<MAX_N; n++){
		comb[n][0] = comb[n][n] = 1;
		for(int k=1; k<n; k++){
			comb[n][k] = comb[n-1][k] + comb[n-1][k-1];
		}
	}

	while(scanf("%lf", &point_prob), point_prob > -EPS){
		solve();
	}

	return 0;
}