SRM408 Div2 Hard

1000

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

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

view plainprint?

1. const int R = 1000 + 1;  
2. const int B = 4000 + 1;  
3.   
4. double memo[R][B];  
5.   
6. double rec(int r, int b)  
7. {  
8.   if (r < 0 || b < 0) return 0;  
9.   
10.   double &ret = memo[r][b];  
11.   if (ret != -1) return ret;  
12.   if (r == 0 && b == 1) return ret = 1.0;  
13.   if (r == 0 && b == 0) return 0;  
14.   
15.   double p = 0;  
16.   
17.   p += rec(r - 1, b - 1) * (double)r / (double)(r + b);  
18.   p += rec(r, b - 2) * (double)b / (double)(r + b);  
19.   
20.   return ret = p;  
21. }  
22.   
23. class MarblesInABag {  
24. public:  
25.   double getProbability(int r, int b)  
26.   {  
27.     if (r < R && b < B) ; else return 0;  
28.     fill(&memo[0][0], &memo[R - 1][B], -1);  
29.     return rec(r, b);  
30.   }  
31. };  

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