TopCoder SRM 537 Div1 Medium: KingXMagicSpells

解法

各ビットについては独立に考えて動的計画法で解く。

コード

public class KingXMagicSpells {
	public double expectedNumber(int[] ducks, int[] one, int[] two, int D) {
		int N = ducks.length;

		int[] from = new int[N];
		for (int i = 0; i < N; i++) {
			from[two[i]] = i;
		}

		double ans = 0.0;
		// day日目にxのiビットがbitである確率を出したい
		for (int i = 0; i < 32; i++) {
			double[][][] dp = new double[D + 1][N][2];
			for (int x = 0; x < N; x++) {
				if ((ducks[x] & (1 << i)) == 0) {
					dp[0][x][0] = 1.0;
				} else {
					dp[0][x][1] = 1.0;
				}
			}

			for (int day = 0; day < D; day++) {
				for (int x = 0; x < N; x++) {
					for (int bit = 0; bit < 2; bit++) {
						dp[day + 1][x][bit] += dp[day][from[x]][bit] * 0.5;
						dp[day + 1][x][bit ^ ((one[x] >> i) & 1)] += dp[day][x][bit] * 0.5;
					}
				}
			}

			ans += dp[D][0][1] * (1 << i);
		}
		return ans;
	}
}