Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-06SRM300台を練習していく part8

SRM 318 CyclicGame

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

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


public class CyclicGame {
	
	public double EPSILON = 0.00000000000001;
	
	public double[][] _memo;
	
	public int[] _cells;
	
	public double dfs(int times, int now) {
		if (times >= 1000) {
			return 0.0d;
		}
		if (_memo[times][now] >= 0) {
			return _memo[times][now];
		}
		
		double exp = 0.0d;
		for (int d = 1 ; d <= 6 ; d++) {
			int toidx = (now + d) % _cells.length;
			int val = _cells[toidx];
			exp += val * 1.0d / Math.pow(6, times) + dfs(times + 1, toidx);
		}
		
		if (exp < 0.0d) {
			exp = 0.0d;
		}
		
		_memo[times][now] = exp;
		return exp;
	}

	public double estimateBank(int[] cells) {
		_cells = cells;
		_memo = new double[1000][15];
		for (int t = 0 ; t < 1000 ; t++) {
			for (int m = 0 ; m < 15 ; m++) {
				_memo[t][m] = -1;
			}
		}
		return dfs(1, 0);
	}
}