Codeforces #301 Div2 D. Bad Luck Island

場合分けの面倒なCより、こっちの方がよっぽど楽でした。
http://codeforces.com/contest/540/problem/D

問題

この島には岩・ハサミ・紙の３種類の生物(?)がいる。
それぞれ現在の数はR,S,Pである。

異なる種類の生物同士が出会うと、じゃんけんの要領で弱い方が1匹死ぬ。
どの生物同士が出会うかは、偶然でありその確率は等しい。

それぞれの生物が１種類だけ残る確率を求めよ。

解法

dp(求めたい生物の数, 好物の敵の数, 天敵の数)としてDPしていくだけ。
岩・ハサミ・紙が残る確率はそれぞれdp(R,S,P), dp(S,P,R), dp(P,R,S)である。

一般化してdp(R,S,P)の求め方を考えると以下の通り。

• 岩が全滅、すなわちR==0ならdo(R,S,P)=0
• 他の生物が全滅、すなわちS+P==0ならdo(R,S,P)=1
• ３種ともに生きてる場合、以下の確率を元にdp(R,S,P)を再帰的に求めればよい。
  • 岩とハサミが出会う確率はRS/(RS+SP+RP)、その時ハサミが１体減る
  • ハサミと紙が出会う確率はSP/(RS+SP+RP)、その時紙が１体減る
  • 紙と岩が出会う確率はRP/(RS+SP+RP)、その時岩が１体減る

double memo[105][105][105];

double dpdp(int R,int S,int P) {
	if(R==0) return 0;
	if(S+P==0) return 1;
	double& ret=memo[R][S][P];
	if(memo[R][S][P]>=0) return ret;
	ret = 0;
	if(R&&S) ret += dpdp(R,S-1,P)*R*S;
	if(S&&P) ret += dpdp(R,S,P-1)*S*P;
	if(R&&P) ret += dpdp(R-1,S,P)*R*P;
	ret /= (R*S+S*P+R*P);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(x,101) FOR(y,101) FOR(i,101) memo[x][y][i]=-1;
	cin>>x>>y>>i;
	_P("%.12lf %.12lf %.12lf\n",dpdp(x,y,i),dpdp(y,i,x),dpdp(i,x,y));
}

まとめ

素直に書けるこちらの方がラクでした。