SRM513 Div1 Medium

500

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

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

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

の4パターンを考える。

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