TopCoder SRM 752 Div1 Medium Literature

解けはしたけど手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=15326

問題

1～3Nのカードを、3人でN枚ずつ持っている。
1番手は、自身のカードをすべて知っているが、他の２人が何を持っているかは知らない。
ここで、３人が順に自分が持っていないカード2N枚のうちどれかの番号を等確率でしゃべる（同じものを複数回話すこともある）。
今、３人のしゃべった履歴が与えられている。

この状態で、１番手が全員のカードを全部認識するには、３人合計で何回しゃべった後か、その期待値をこたえよ。

解法

１人目のカードはわかっているので、２人目の発言は３人目の、３人目の発言は２人目の未確定カードを言い当てる可能性がある。
f(A,B) := 次に２人目がしゃべる番であるとき、2人目の未確定カードがA枚、3人目の未確定カードがB枚とする場合で、１番手が全員のカードを認識するまでの期待値
とする。これを頑張って求めよう。

さて、この類の問題で、「１枚引いて有効なカードが来る確率がpの時、期待値1/p枚で有効なカードが来て次の状態に進む」という定番テクがある。
ただ今回は３人でカードを引いているので、少しややこしい。
２人目と３人目が一気にカードを引いたとする。
少なくとも片方が相手の未確定カードを引く確率をpとすると、有効カードを引くまで3/p-3枚かかる。
あとは

• ２人目が３人目の未確定カードを引き、３人目は２人目の未確定カードを引き当てなかった
• ３人目が２人目の未確定カードを引き、２人目は３人目の未確定カードを引き当てなかった
• ともに相手の未確定カードを引き当てた

場合の期待値を足そう。

class Literature {
	public:
	int N;
	double hoge(int A,int B) {
		assert(A && B);
		if(memo[A][B]>=0) return memo[A][B];
		double ret=0;
		double add=3*(2*N)*(2*N)*1.0/(2*N*(A+B)-A*B)-3;
		
		double AB=1.0*A*B/(2*N*(A+B)-A*B);
		double Ab=1.0*A*(2*N-B)/(2*N*(A+B)-A*B);
		double aB=1.0*(2*N-A)*B/(2*N*(A+B)-A*B);
		
		// oo
		if(A==1 && B==1) {
			ret+=(AB+Ab)*(add+1);
			ret+=aB*(add+2);
		}
		else if(A==1) {
			ret+=(AB+Ab)*(add+1);
			ret+=aB*(add+3+hoge(A,B-1));
		}
		else if(B==1) {
			ret+=(AB+aB)*(add+2);
			ret+=Ab*(add+3+hoge(A-1,B));
		}
		else {
			ret+=AB*(add+3+hoge(A-1,B-1));
			ret+=Ab*(add+3+hoge(A-1,B));
			ret+=aB*(add+3+hoge(A,B-1));
		}
		
		
		return memo[A][B]=ret;
	}
	
	double expectation(int n, vector <int> Teja, vector <int> history) {
		int did[3030]={};
		N=n;
		int lef[2]={N,N};
		FORR(a,Teja) did[a]=1;
		int i;
		FOR(i,history.size()) {
			if(did[history[i]]) continue;
			if(i%3==0) continue;
			did[history[i]]=1;
			if(i%3==1) lef[1]--;
			if(i%3==2) lef[0]--;
			if(lef[0]==0 || lef[1]==0) return i+1;
		}
		int cur=history.size();
		
		int x,y;
		FOR(x,1010) FOR(y,1010) memo[x][y]=-1;
		
		
		
		if(cur%3==0) cur++;
		
		if(cur%3==1) return cur+hoge(lef[1],lef[0]);
		else return cur+lef[0]*1.0/(2*N)*(lef[0]==1?1:(2+hoge(lef[1],lef[0]-1)))+(2*N-lef[0])*1.0/(2*N)*(2+hoge(lef[1],lef[0]));
	}
}

まとめ

状態遷移がややこしかった。
１発で通ったけど、結構時間がかかったので本番出てたら結構苦戦してそう。