いろはちゃんコンテスト Day2 : F - 総入れ替え

これは面倒ではあるけど解法は割と単純だよね。
https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_f

問題

3つの箱があり、それぞれ50円と100円玉がいくつか入っている。
2人で交互に、箱を1つ選び中のコインをランダムで1枚抜き出す、ということを行う。
両者の選んだ箱と抜き出したコインは両者とも知っているものとする。

互いに自身の獲得金額を最大化しようとするとき、先手の獲得金額の期待値はいくらになるか。

解法

各コイン枚数は10枚以下なので、11^6通りメモ化再帰すればよい。
「相手に最大何円差をつけられるか」で考えると先手後手を気にしなくて良くなるので実装が楽。

int A[2],B[2],C[2];
double memo[11][11][11][11][11][11];

double hoge(int a1,int a2,int b1,int b2,int c1,int c2) {
	if(a1+a2+b1+b2+c1+c2==0) return 0;
	if(memo[a1][a2][b1][b2][c1][c2]>-1000000) return memo[a1][a2][b1][b2][c1][c2];
	
	double ma=-101010101;
	if(a1+a2>0) {
		double pat;
		if(a1==0) pat=50-hoge(a1,a2-1,b1,b2,c1,c2);
		if(a2==0) pat=100-hoge(a1-1,a2,b1,b2,c1,c2);
		if(a1&&a2) pat=((100-hoge(a1-1,a2,b1,b2,c1,c2))*a1+(50-hoge(a1,a2-1,b1,b2,c1,c2))*a2)/(a1+a2);
		ma=max(ma,pat);
	}
	if(b1+b2>0) {
		double pat;
		if(b1==0) pat=50-hoge(a1,a2,b1,b2-1,c1,c2);
		if(b2==0) pat=100-hoge(a1,a2,b1-1,b2,c1,c2);
		if(b1&&b2) pat=((100-hoge(a1,a2,b1-1,b2,c1,c2))*b1+(50-hoge(a1,a2,b1,b2-1,c1,c2))*b2)/(b1+b2);
		ma=max(ma,pat);
	}
	if(c1+c2>0) {
		double pat;
		if(c1==0) pat=50-hoge(a1,a2,b1,b2,c1,c2-1);
		if(c2==0) pat=100-hoge(a1,a2,b1,b2,c1-1,c2);
		if(c1&&c2) pat=((100-hoge(a1,a2,b1,b2,c1-1,c2))*c1+(50-hoge(a1,a2,b1,b2,c1,c2-1))*c2)/(c1+c2);
		ma=max(ma,pat);
	}
	
	return memo[a1][a2][b1][b2][c1][c2]=ma;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A[0]>>A[1];
	cin>>B[0]>>B[1];
	cin>>C[0]>>C[1];
	
	int D[6];
	FOR(D[0],11)
	FOR(D[1],11)
	FOR(D[2],11)
	FOR(D[3],11)
	FOR(D[4],11)
	FOR(D[5],11) memo[D[0]][D[1]][D[2]][D[3]][D[4]][D[5]]=-10101010;
	
	double sum=A[0]*100+A[1]*50+B[0]*100+B[1]*50+C[0]*100+C[1]*50;
	double ret=hoge(A[0],A[1],B[0],B[1],C[0],C[1]);
	_P("%.12lf\n",sum-(sum-ret)/2);
}

まとめ

こういうの実装ミスが怖い。