Autumn Fest 2012 : C Cards

さて３問目。
ここまでは本番に何とか解けた。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_03

カードゲームをしてスコアの期待値を求める問題。
２枚裏返す→１枚表に戻す、と表裏が行き来するのが独特。
とはいえ、裏返し→表返しで合計１枚裏になるので、いずれ終了する。

この問題では、２枚選んで裏返す場合と、１枚表に戻す場合を交互にメモ化再帰させることになる。
関数の引数はカードの表裏の状態をbitmapで表したもの。
この問題はN<=20なので、2^20回の計算で済むので計算量は問題ない。

２枚裏返す処理では、今表のものから２枚選ぶケースを列挙し、それぞれのスコアの平均をとる。
１枚表に戻す処理では、裏のものから１枚選ぶケースを列挙し、それぞれのスコアの平均をとる。
全部表の状態から、１枚除き裏になるまで上の２パターンを繰り返せばよい。

int N;
int X[30];

double OM[1<<20];
double UR[1<<20];

int bitcount(int n) {
	int i=0;
	while(n>0) {i += n%2; n>>=1;}
	return i;
}

double ura(int mask) ;
double omote(int mask) {
	int x,y,c;
	double t;
	if(OM[mask]<0) {
		if(bitcount(mask)>=N-1) {
			OM[mask]=0;
		}
		else {
			t=c=0;
			FOR(x,N) {
				if(mask & (1<<x)) continue;
				for(y=x+1;y<N;y++) {
					if(mask & (1<<y)) continue;
					
					c++;
					t += ura(mask | ((1<<x)|(1<<y)));
				}
			}
			OM[mask] = t/c;
		}
	}
	return OM[mask];
}
double ura(int mask) {
	int i,c;
	double t;
	if(UR[mask]<0) {
		t=c=0;
		FOR(i,N) {
			if(mask & (1<<i)) {
				c++;
				t += X[i]+omote((mask ^ (1<<i)));
			}
		}
		if(c==0) UR[mask]=0;
		else UR[mask] = t/c;
	}
	return UR[mask];
}

void solve() {
	int x,y,i,j,p,rr,TM,TTC;
	
	N=GETi();
	FOR(i,N) X[i]=GETi();
	FOR(i,1<<20) {
		OM[i]=UR[i]=-1;
	}
	
	_P("%.9f\n",omote(0));
	return;
}

まとめ

２つの再帰を繰り返すってのが面白いね。
これ、カードが表裏行ったり来たりするけどうまくDPで書けるのかな？

GCJ 2009でもこういう問題あったよね。
http://code.google.com/codejam/contest/188266/dashboard#s=p2