SRM 513 Div1 Med PerfectMemory

SRM
問題概要

記憶力がすごい人がNM枚のカードで神経衰弱をした時のゲーム終了時までのターン数の期待値を求めよ。

dp[i][j]:=全く見たことないのがi組、片方だけ見たことあるのがj組のときの終了までのターン数の期待値

dp[i][j]からの状態遷移は残ってる2i+j枚の中から

  • 今までに見たことのあるj枚のどれかを引く
  • 見たことない2i枚のどれかを引き、次に前に引いたものと同じものを引く
  • 見たことない2i枚のどれかを引き、次に今までに見たことのあるb枚のどれかを引く
  • 見たことない2i枚のどれかを引き、次に見たことない2i-2枚のどれかを引く

のどれか。

class PerfectMemory
{
	public:
	double dp[2000][2000];
	double rec(int a,int b)
	{
		if(dp[a][b]!=0)return dp[a][b];
		if(a==0&&b==0)return 0.0;
		dp[a][b]=1.0;
		double A = 2*a;
		double B = b;
		double S = 2*a+b;
		if(b>0)dp[a][b]+=B/S*rec(a,b-1);
		if(a>0)dp[a][b]+=A/S/(S-1)*rec(a-1,b);
		if(a>0)dp[a][b]+=A/S*B/(S-1)*(1.0+rec(a-1,b));
		if(a>1)dp[a][b]+=A/S*(A-2)/(S-1)*rec(a-2,b+2);
		return dp[a][b];
	}
	double getExpectation(int N, int M)
	{
		return rec(N*M/2,0);
	}
};