TopCoder SRM 511 Div1 Medium FiveHundredEleven

SRM511はDiv2 HardとDiv1 Mediumが同じ。
http://community.topcoder.com/stat?c=problem_statement&pm=11484

問題

数字が書かれたカードがN枚ある。
これらカードを交互に取り合うゲームを行う。
このゲームは以下のように進む。

• 自分の手番では残されたカードのうち１枚を取らなけばならない。
  • 自分の手番の時にカードがなくなってたら負け。
  • カードを取ったとき、それまでに両者が取り除いたカードの数値のorが511になったら負け。

両者が最適手を取った場合、勝者はどちらか答えよ。

解法

本番アプローチはおおむねあってたが、最後まで詰め切れず他の解答を参考にした。

取り除かれたカードのorの値に対し、それ以外のbitがセットされたカードはまだどちらも取っていないことになる。
それ以外のカードは残っているかもしてないし、取り除かれてるかもしれないのでその枚数は不明)

よって、状態として(取り除かれたカードのorの値, すでに取ったカードの枚数)を持ちbitDPしよう。
それぞれの手番では、カードのorの値を変化させるカードを新規にとってもいいし、orの値を変化させないカードがまだ残っているならそれをとっても良い。

状態数は511*50程度で、選ぶカードの選択肢も50枚なので計算時間は余裕。

int win[512][52];

class FiveHundredEleven {
	public:
	int N;
	vector<int> C;
	int dpdp(int mask,int step) {
		if(mask==511) return 1; // win
		if(step==N) return 0; // lose
		
		if(win[mask][step]==-1) {
			int numinc=0,x;
			win[mask][step] = 0;
			
			FOR(x,N) if((mask|C[x])==mask) numinc++;
			win[mask][step] |= (step<numinc && dpdp(mask,step+1)==0);
			FOR(x,N) win[mask][step] |= ((mask|C[x])!=mask && dpdp(mask|C[x],step+1)==0);
		}
		return win[mask][step];
	}
	
	string theWinner(vector <int> cards) {
		int i,j,x,y;
		C=cards;
		N=cards.size();
		
		MINUS(win);
		return dpdp(0,0)?"Fox Ciel":"Toastman";
	}
};

まとめ

自分が最初解いたときは、(すでに取ったカードの枚数)ではなく(すでに取ったカードの枚数の偶奇)で処理してうまくいかなかった。