SRM 656 Div. 1 Easy: RandomPancakeStack (DP・期待値)
解法
dp[i][j]:= i番目にjのパンケーキが置かれる確率を3重ループを回して求めておき、最後に各パンケーキの美味しさを期待値を出す。
1310 -> 1473 (+163)
コード
import java.util.Arrays; public class RandomPancakeStack { public double expectedDeliciousness(int[] d) { int N = d.length; double[][] dp = new double[N][N]; Arrays.fill(dp[0], (double) 1 / N); for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N - i; j++) { for (int k = 0; k < j; k++) { dp[i + 1][k] += (double) dp[i][j] / (N - i - 1); } } } double ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ans += dp[i][j] * d[j]; } } return ans; } }