SRM 478 div2 hard:RandomAppleEasy

問題

TopCoder Statistics - Problem Statement

解法

dp[n][r][g] = (n 個目の箱の時点で, 赤色のりんごが r 個, 緑色のりんごが g 個入っているような場合の数) という dp は簡単に解けます。これがわかれば, 求める確率は, dp[N][r][g]/(2^n-1) * r/(r+g) を各組 (r, g) について求めた和になります。

ll dp[2][505][505];

class RandomAppleEasy {
public:
    double theRed(vector <int> red, vector <int> green) {
        memset(dp, 0, sizeof(dp));
        int n = red.size();
        dp[0][0][0] = 1;
        for (int i = 0; i < n; i++) {
            int cur = i%2, tar = cur^1;
            for (int j = 0; j <= 500; j++) for (int k = 0; k <= 500; k++) {
                dp[tar][j][k] = 0;
            }
            for (int j = 0; j <= 500; j++) for (int k = 0; k <= 500; k++) {
                if (dp[cur][j][k] == 0) continue;
                dp[tar][j][k] += dp[cur][j][k];
                dp[tar][j+red[i]][k+green[i]] += dp[cur][j][k];
            }
        }
        double ans = 0;
        for (int i = 0; i <= 500; i++) for (int j = 0; j <= 500; j++) {
            if (i+j == 0) continue;
            ans += 1.*dp[n%2][i][j]/((1ll<<n)-1) * (1.*i/(i+j));
        }
        return ans;
    }
};