Typical DP Contest C: トーナメント (動的計画法)
解法
やるだけ。
コード
import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] arg) { int K = nextInt(); int N = 1 << K; int[] rating = new int[N]; for (int i = 0; i < N; ++i) { rating[i] = nextInt(); } double[][] dp = new double[K + 1][N]; Arrays.fill(dp[0], 1.0); for (int i = 1; i <= K; ++i) { for (int j = 0; j < N; ++j) { double sum = 0; int start = j / (1 << i) * (1 << i); if (j < start + (1 << (i - 1))) { start += 1 << (i - 1); } for (int k = start; k < start + (1 << (i - 1)); ++k) { sum += dp[i - 1][k] / (1 + Math.pow(10, (rating[k] - rating[j]) / 400.0)); } dp[i][j] = dp[i - 1][j] * sum; } } for (int i = 0; i < N; ++i) { System.out.println(dp[K][i]); } } static int nextInt() { int c; try { c = System.in.read(); while (c != '-' && (c < '0' || c > '9')) c = System.in.read(); if (c == '-') return -nextInt(); int res = 0; while (c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = System.in.read(); } return res; } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } return -1; } }