Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-27SRM300台を練習していく part2

SRM 304 Conditional

|  SRM 304 Conditional - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 304 Conditional - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6412

条件付き確率。分母はメモ化再帰で求められる。

メモ化再帰の際、探索中に既に条件

「値がvのサイコロを少なくともひとつは使う」

を満たしたかを示すフラグ isok を用意する。


public class Conditional {

	public double[][][] memo;

	public int _side;

	public int _v;

	public double search(int n, int v, boolean isok) {
		if (v <= 0) {
			if (isok) {
				return 1.0d;
			} else if (n >= 1) {
				double a = 1.0d;
				for (int i = 0 ; i < n ; i++) {
					a *= (double)(_side - 1) / _side;
				}
				return 1.0d - a;
			} else {
				return 0.0d;
			}
		}
		if (n == 0) {
			return 0.0d;
 		}
		double prob = 0.0d;
		int is = isok ?  1 : 0;
		if (memo[n][v][is] >= 0) {
			return memo[n][v][is];
		}
		for (int i = 1 ; i <= _side ; i++) {
			boolean next = (i == _v) || isok;
			prob += search(n-1, v-i, next) / _side;
		}
		memo[n][v][is] = prob;
		return prob;
	}

	public double probability(int nDice, int maxSide, int v, int theSum) {
		memo = new double[nDice+1][theSum+1][2];
		for (int i = 0 ; i <= nDice ; i++) {
			for (int j = 0 ; j <= theSum ; j++) {
				memo[i][j][0] = -1.0d;
				memo[i][j][1] = -1.0d;
			}
		}
		_side = maxSide;
		_v = v;
		double a = search(nDice, theSum, false);
		double b = 1.0d;
		if (maxSide > 1) {
			for (int i = 0 ; i < nDice ; i++) {
				b *= (double)(maxSide - 1) / maxSide;
			}
		} else {
			b = 0.0d;
		}
		System.out.println(a);
		System.out.println(1.0d - b);
		return a / (1.0d - b);
	}

}