MarblesInABag

最初は再帰で考えて

class MarblesInABag {
  double gp(int rc, int bc){
    if(rc > bc) return (double) 0;
    if(rc == 0) return (double) 1;
    if(rc == 1 && bc == 0) return (double) 0;
    return (double) rc /(rc+bc) * gp(rc-1,bc-1) 
    + (double) bc/(rc+bc) * gp(rc, bc-2);
  }
public:
  double getProbability(int redCount, int blueCount) {
    return gp(redCount,blueCount);
  }
};

でこれをメモ化すればいいと思ってたんだけど、それだと、4000*4000の配列を用意しないといけないのでダメだということに気づいた。

というよりここがスタートでO(N^2)をO(N)にするというのが問題の意図だったらしい。

トップのヒトの解答をみると2*5000の配列にしていて赤が一個の時の確率から始まって赤の数を増やしながら、表を更新していた。

ここでのループで解く場合というやりかたになるのかな。