SRM408 Div2 Hard

1000

memo[ 4000 + 1 ][ 4000 + 1 ] だとメモリでアウト

赤を数千回連続で引く確率は十分小さいので、
memo[ 1000 + 1 ][ 4000 + 1 ] くらいでやればいい。

const int R = 1000 + 1;
const int B = 4000 + 1;

double memo[R][B];

double rec(int r, int b)
{
  if (r < 0 || b < 0) return 0;

  double &ret = memo[r][b];
  if (ret != -1) return ret;
  if (r == 0 && b == 1) return ret = 1.0;
  if (r == 0 && b == 0) return 0;

  double p = 0;

  p += rec(r - 1, b - 1) * (double)r / (double)(r + b);
  p += rec(r, b - 2) * (double)b / (double)(r + b);

  return ret = p;
}

class MarblesInABag {
public:
  double getProbability(int r, int b)
  {
    if (r < R && b < B) ; else return 0;
    fill(&memo[0][0], &memo[R - 1][B], -1);
    return rec(r, b);
  }
};