OUPC2012 問題F Game (AOJ2355)
制約条件
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; }