TopCoder SRM 606 Div2 Hard EllysCandyGame

950ptということで少し楽。
http://community.topcoder.com/stat?c=problem_statement&pm=12394

問題

N個の箱が並んでおり、それぞれsweets[i]個の飴が入っている。
ここで、２人で交互に以下の手順で箱を選ぶゲームを行う。

• 箱を選ぶと、中身の飴を全部もらえる。その時、両隣の箱の飴の数が倍になる。
• 中身が空の箱は選べない。全部の箱が空になったらゲームが終了。所有する飴が多いプレイヤーが勝ち。

最適手を取ったときの勝者を答えよ。

解法

N<=10、ということで、箱の状態をbitmaskで表現し、bitDPをすればよい。
飴が残っている箱をbitmaskで表現すると、その時がどちらの手順かと、あと残された飴が倍になったかどうかがわかる。
先手は差を最大化、後手は差を最小化していくだけ。

初期状態で飴が0個の箱がある点に注意。

int dpdp[1<<10];

class EllysCandyGame {
	public:
	string getWinner(vector <int> sweets) {
		int N=sweets.size();
		int i,j,x,y,mask;
		int cs[10];
		
		dpdp[0]=0;
		dpdp[1<<N]=0;
		for(mask=1;mask<1<<N;mask++) {
			int ng=0,step=0;
			FOR(i,N) ng |= (mask&(1<<i)) && sweets[i]==0;
			if(ng) continue;
			
			FOR(i,N) if((mask&(1<<i))==0 && sweets[i]) step++;
			if(step%2) dpdp[mask]=1<<25;
			else dpdp[mask]=-1<<25;
			
			FOR(i,N) if((mask&(1<<i))) {
				int sc=sweets[i];
				if(i>0 && sweets[i-1] && (mask&(1<<(i-1)))==0) sc*=2;
				if(i<N-1 && sweets[i+1] && (mask&(1<<(i+1)))==0) sc*=2;
				if(step%2) dpdp[mask]=min(dpdp[mask],dpdp[mask ^ (1<<i)]-sc);
				else dpdp[mask]=max(dpdp[mask],dpdp[mask ^ (1<<i)]+sc);
			}
			
			if(step==0) break;
		}
		
		if(dpdp[mask]>0) return "Elly";
		if(dpdp[mask]<0) return "Kris";
		return "Draw";
		
	}
};

まとめ

N<=10だしあからさまにbitDPな問題。