2139 - Memory Match

AOJ
問題

２枚ずつのM種類のカードN(=2M)枚で１人神経衰弱をする。
今までに開けたカード全てを記憶出来るとき、ミスマッチする回数の期待値を求めよ。

制約

2<=N<=1000

解法

カードを１列に並べたものをイメージして、左から順に開けていく。
今開けようとしているカードの位置、１回開けたがまだマッチしていないカードの枚数を引数としてメモ化再帰。

ソース
double memo[1000][1000];
int n;
double solve(int now, int rest) { // rest : 開けたけど残っているもの
  if (now >= n) return 0;
  if (memo[now][rest] >= 0) return memo[now][rest];
  int num = rest+1;
  double res = 0;
  double p = (double)rest/(n-now);
  if (rest) {
    res += solve(now+1, rest-1) * p; // 既に開けた奴とマッチ
  }
  // 1枚目が初めて
  p = 1-p;
  if (rest != n-now) {
    // 2枚目が既に開けたやつ
    double q = (double)rest/(n-now-1);
    if (rest) {
      res += (1 + solve(now+2, rest)) * p * q;
    }
    // 2枚目も初めて
    q = double(n-now-1-rest-1)/(n-now-1);
    if (n-now-1-rest-1) {
      res += (1 + solve(now+2, rest+2)) * p * q;
    }
    // 2枚目が同じ
    q = 1.0/(n-now-1);
    res += solve(now+2, rest) * p * q;
  }
  return memo[now][rest] = res;
}

int main() {
  while(cin>>n,n) {
    REP(i,n)REP(j,n) memo[i][j] = -1;
    printf("%.10f\n", solve(0,0));
  }
}