SRM 477 Div2 Hard RandomAppleEasy

問題

http://community.topcoder.com/stat?c=problem_statement&pm=10562
箱がN個あり、箱iにある赤りんごの数と青りんごの数がそれぞれred[i], green[i]で与えられる。この複数の箱から空集合を除く箱の部分集合を選んで、それらの選ばれた箱にあるすべてのりんごを一つの箱にまとめる。そこから一つりんごを取り出した時にそれが赤りんごである確率を求めよ。ただし、どの部分集合も同じ確率で選ばれるとし、まとめた箱にあるどのりんごも同じ確率で取り出されるものとする。

やりかた

practice roomの複数の回答を参考にしました。

DP。
dp[i][j] := （すべての部分集合を列挙した時に、赤りんごの数の合計がi、青りんごの数の合計がjになるケース数）でDP。
赤りんごがi個で青りんごがｊ個の場合に赤りんごが選ばれる確率はi / (i + j)となるので、答えはこれにDPで求めたパターン数をかけたものの合計を部分集合数2^N - 1で割ればいい。

ll dp[501][501];

class RandomAppleEasy {
public:
  double theRed(vector <int> red, vector <int> green) {
    int N = red.size();
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 0; i < N; i++)
      for(int j = 490; j >= 0; j--)
	for(int k = 490; k >= 0; k--)
	  dp[j + red[i]][k + green[i]] += dp[j][k];

    double ret = 0.0;
    for(int i = 1; i <= 500; i++)
      for(int j = 1; j <= 500; j++)
	ret += (double)dp[i][j] * i / (i + j);
	
    ret /= (1LL << N) - 1;
    return ret;
  }
};

こういったdpはやったことがあったはずだが、今回使うべきだとはわからなかった。勉強になった。