Typical DP Contest C: トーナメント (動的計画法)

問題

C: トーナメント - Typical DP Contest | AtCoder

解法

やるだけ。

コード

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;
	}

}