OUPC2012 問題F Game (AOJ2355)

問題

日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2355

制約条件

n≦8
-10^5≦f≦10^5
-10^5≦xi≦10^5

方針

勝てる場合は手数を最小化、負ける場合は手数を最大化するゲーム木探索なので、
勝ちの場合の点数をinf-turn
引き分けの点数をinf/2
負けの点数をturn
とした上でminmax探索をすればいい。


ただしそのままだと間に合わないので、αβカットをする。
ゲーム終了判定(どうやっても勝てない場合はギブアップする)は、
事前にビットDPにより、その状態から、相手が舐めプした時に得られる点数をあらかじめ計算しておいて、その点数をもらっても勝てないならギブアップとする。


下のコードでは、
dp1[i][j]が、ビットの状態iで、最後に選ばれた数がjの状態から先手が本気を出して、後手が舐めプしたときの最大得点、
dp2[i][j]が、後手が本気出して、先手が舐めプした時の最大得点としてある。

ソースコード

inline void takemax(int &a,int b){if(a==-inf||a<b)a=b;}

int n,f,x[8][8];
int dp1[1<<16][8],dp2[1<<16][8];
int rec(int b1,int b2,int last,int pt,int turn,int a,int b){
	if(turn==2*n+1){
		if(pt==0)return inf/2;
		if(pt>0)return inf-turn;
		return turn;
	}
	if(turn%2==1){
		if(pt+dp1[b1<<n|b2][last]<0)return turn;
		rep(i,n)if(!(b1&1<<i)){
			a=max(a,rec(b1|1<<i,b2,i,pt+(turn>1?x[i][last]:0),turn+1,a,b));
			if(a>=b)return b;
		}
		return a;
	}
	else{
		if(pt-dp2[b1<<n|b2][last]>0)return inf-turn;
		rep(i,n)if(!(b2&1<<i)){
			b=min(b,rec(b1,b2|1<<i,i,pt-x[last][i],turn+1,a,b));
			if(a>=b)return a;
		}
		return b;
	}
}


int main(){
	cin>>n>>f;
	rep(i,n)rep(j,n)cin>>x[i][j];
	rep(i,1<<2*n)rep(j,n)dp1[i][j]=dp2[i][j]=-inf;
	rep(j,n)dp1[(1<<2*n)-1][j]=dp2[(1<<2*n)-1][j]=0;
	
	for(int i=(1<<2*n)-1;i>=0;i--){
		int cnt=__builtin_popcount(i);
		if(cnt%2==0){
			rep(j,n)rep(k,n)if(!(i&1<<k+n))
			takemax(dp1[i][j],dp1[i^1<<k+n][k]+(cnt?x[k][j]:0)),
			takemax(dp2[i][j],dp2[i^1<<k+n][k]-(cnt?x[k][j]:0));
		}
		else{
			rep(j,n)rep(k,n)if(!(i&1<<k))
			takemax(dp1[i][j],dp1[i^1<<k][k]-x[j][k]),
			takemax(dp2[i][j],dp2[i^1<<k][k]+x[j][k]);
		}
	}
	
	int ans=rec(0,0,0,f,1,-inf,inf);
	if(ans==inf/2)cout<<"Draw\n"<<n*2<<endl;
	else if(ans>inf/2)cout<<"First\n"<<inf-ans<<endl;
	else cout<<"Second\n"<<ans<<endl;
	
	return 0;
}