TopCoder SRM 513 Div1 Medium PerfectMemory

これまたすんなり解けたMedium。
http://community.topcoder.com/stat?c=problem_statement&pm=11500

問題

N*M枚のカードがあり、その中で同じ種類のカードが2枚ずつある。
このカードで完全に記憶力のある人が神経衰弱を行う場合、全カード取得までのターン数の期待値はいくらか。

解法

状態として[1枚も出てきてない組][1枚出てきた組]を持ちDPしていくだけ。

状態遷移として以下の4つが考えられる。

• 1枚目に過去出てきたことがある種類のカードが出たら、2枚目でその組を取り除く。
• 1枚目に過去出てきたことがない種類のカードが出たら：
  • 2枚目で知ってるカードが出たら、次のターンで知ってるカードを取り除く。
  • 2枚目で別の知らないカードが出たら、次のターンで知ってるカードが2枚増えたと考えて続ける。
  • たまたま2枚目で1枚目と同じカードが出たら、その組を取り除く。

各状態で4通りに状態遷移するので、計算量はO(N^2*M*2)である。

double memo[1500][1500];
class PerfectMemory {
	public:
	int C;
	
	
	double calc(int uk, int k) {
		if(memo[uk][k]>=0) return memo[uk][k];
		if(uk==0) return k;
		int tc=2*(uk+k);
		
		memo[uk][k]=1;
		// k
		if(k>0) memo[uk][k] += k/(double)(tc-k)*calc(uk,k-1);
		// uk,k
		memo[uk][k] += 2*uk/(double)(tc-k)*k/(double)(tc-k-1)*(calc(uk-1,k)+1);
		// uk,same
		memo[uk][k] += 2*uk/(double)(tc-k)*1/(double)(tc-k-1)*calc(uk-1,k);
		// uk,uk(dif)
		if(uk>1) memo[uk][k] += 2*uk/(double)(tc-k)*(2*uk-2)/(double)(tc-k-1)*calc(uk-2,k+2);
		return memo[uk][k];
	}
	
	double getExpectation(int N, int M) {
		int x,y;
		C=N*M/2;
		FOR(x,1500) FOR(y,1500) memo[x][y]=-1;
		
		return calc(C,0);
	}
}

まとめ

最初からカード枚数C=N*Mを与えればいいのに、なぜN*Mと2変数にしたんだろう。