hama_DU@TopCoderへの道

SRM 313 CrazyRunning

Java, div1q2 |

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

まったく分からなかった。editorial見て実装

public class CrazyRunning {

	public double first;
	public double others;
	
	public double[] memo;
	
	public double EPSILON = 0.0000000000000001;
	
	public double rec(int total, int left) {
		if (left == 0) {
			return -others;
		}
		if (memo[left] != 0) {
			return memo[left];
		}
		
		double ans = 0.0d;
		double pp = 1.0d;
		double p0 = (double) left / (total - 1);
		double p1 = (double) (total - left - 2) / (total - 1);
		double p2 = 1.0d / (total - 1);
		double p20 = p2 * left / (total - 1);
		double p21 = p2 * (total - 1 - left) / (total - 1);

		while (pp > EPSILON) {
			ans += pp * p0 * (others * 2 + rec(total, left-1));
			ans += pp * p20 * (first * 2 + others * 2 + rec(total, left-1));
			ans += pp * p1 * (others * 2);
			ans += pp * p21 * (first * 2 + others * 2);
			pp *= (p1 + p21);
		}
		memo[left] = ans;
				
		return ans;
	}
	
	public double expectedTime(int[] corridors) {
		int len = corridors.length;

		first = corridors[0];
		for (int i = 1 ; i < len ; i++) {
			others += corridors[i];
		}
		others = others / (double)(len - 1);
		memo = new double[100];
				
		return first + others * 2 + rec(len, len-2);
	}

}