2011-08-05SRM300台を練習していく part7
SRM 313 CrazyRunning
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); } }
コメント