Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-11-23SRM488(DIV1)

SRM488 第一問(250pt) TheBoredomDivOne

|  SRM488 第一問(250pt) TheBoredomDivOne - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM488 第一問(250pt) TheBoredomDivOne - hama_DU@TopCoderへの道

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

  • 期待値をメモ化すればおk。
  • 時間はかかったが解けた。120点ぐらい

public class TheBoredomDivOne {
	public double[][] ex;

	public double calc(int n, int m) {
		if (m <= 0) {
			return 0;
		}
		if (ex[n][m] > 0) {
			return ex[n][m];
		}
		double all = (n + m) * (n + m - 1) / 2;
		double zero = n * (n - 1) / 2 / all;
		double two = m * (m - 1) / 2 / all;
		double one = 1 - (zero + two);

		double ans = (zero + one * (1 + calc(n+1, m-1)) + two * (1 + calc(n+2, m-2))) / (one + two);
		ex[n][m] = ans;
		return ans;
	}

	public double find(int n, int m) {
		ex = new double[100][100];
		ex[1][1] = 1.0;
		ex[2][1] = 1.5;
		ex[1][2] = 2.0;
		return calc(n, m);
	}
}