SRM513 Div1 Medium

500

memo[両方の位置が特定されていない組みの数][片方の位置が特定されていない組みの数] = 期待値

全ての位置を記憶できるという事は、あるターンで最初にめくるカードはまだ一度もめくっていない位置を選ぶのが最適。
絵が合わなかった場合、もう片方が出るまではずっと放置することになる。

"初めてめくるカード" -> "初めてめくるカード" (運良く同じ絵)
"初めてめくるカード" -> "初めてめくるカード" (違う絵)
"初めてめくるカード" -> "もう片方の位置が分かるカード"
"もう片方の位置が分かるカード" -> "もう片方のカード"

の4パターンを考える。

view plainprint?

1. const int H = 50 + 1;  
2. const int W = 50 + 1;  
3. const int P = H * W;  
4.   
5. double memo[P][P];  
6. double rec(int both, int half)  
7. {  
8.   double& ret = memo[both][half];  
9.   if (ret != -1) return ret;  
10.   if (both == 0 && half == 0) return 0;  
11.   
12.   double sum = 0;  
13.   
14.   double closed = both * 2 + half;  
15.   double w = (closed - half) / closed;  
16.   
17.   if (1 <= both) { // hit  
18.     double p = 1.0 / (closed - 1.0) * w;  
19.     sum += (1.0 + rec(both - 1, half)) * p;  
20.   }  
21.   
22.   if (2 <= both) { // miss  
23.     double p = (closed - half - 2.0) / (closed - 1.0) * w;  
24.     sum += (1.0 + rec(both - 2, half + 2)) * p;  
25.   }  
26.   
27.   if (1 <= both && 1 <= half) { //  
28.     double p = 1.0 * half / (closed - 1.0) * w;  
29.     sum += (2.0 + rec(both - 1, half)) * p;  
30.   }  
31.   
32.   if (half) {  
33.     double p = 1.0 * half / closed;  
34.     sum += (1.0 + rec(both, half - 1)) * p;  
35.   }  
36.   
37.   return ret = sum;  
38. }  
39.   
40. class PerfectMemory {  
41. public:  
42.   double getExpectation(int N, int M)  
43.   {  
44.     fill(&memo[0][0], &memo[P - 1][P - 1] + 1, -1);  
45.     return rec(N * M / 2, 0);  
46.   }  

const int H = 50 + 1;
const int W = 50 + 1;
const int P = H * W;

double memo[P][P];
double rec(int both, int half)
{
  double& ret = memo[both][half];
  if (ret != -1) return ret;
  if (both == 0 && half == 0) return 0;

  double sum = 0;

  double closed = both * 2 + half;
  double w = (closed - half) / closed;

  if (1 <= both) { // hit
    double p = 1.0 / (closed - 1.0) * w;
    sum += (1.0 + rec(both - 1, half)) * p;
  }

  if (2 <= both) { // miss
    double p = (closed - half - 2.0) / (closed - 1.0) * w;
    sum += (1.0 + rec(both - 2, half + 2)) * p;
  }

  if (1 <= both && 1 <= half) { //
    double p = 1.0 * half / (closed - 1.0) * w;
    sum += (2.0 + rec(both - 1, half)) * p;
  }

  if (half) {
    double p = 1.0 * half / closed;
    sum += (1.0 + rec(both, half - 1)) * p;
  }

  return ret = sum;
}

class PerfectMemory {
public:
  double getExpectation(int N, int M)
  {
    fill(&memo[0][0], &memo[P - 1][P - 1] + 1, -1);
    return rec(N * M / 2, 0);
  }