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