SRM 511 Div1 Medium FiveHundredEleven

問題

メモリとカードを使ったゲームをする。
二人のプレイヤーが交互に、

  • カードを選んで取り除く。
  • カードに書かれている数字をa、メモリの数字をxとしたときx=x|aと置き換える
  • 自分の手番でカードが全てなくなっていたら負け
  • 自分の手番の後でメモリの値が511になったら負け

お互いが最善を尽くすとき、どちらのプレイヤーが勝つか求めよ。

制約条件

カードの枚数≦50,
カードに書かれている数字≦511

方針1

カードの数字のビットのうち、メモリで立っているビットはもうメモリに影響を与えないので、カードの数字のビットがそこだけなくなったと考える。

たとえばメモリが1101(2)なら、0111(2)のカードは0010(2)のカードとみなせる。
ので、カードの数字を書き換えてしまう。


ついでにカードは小さい順にソートする。すると状態数が大分小さくなる。
これで全カードを記憶する無理矢理なメモ化再帰

ソースコード

本番で通したコード。

map<pair<int,vi>,bool> memo;
bool rec(int m,vi cd){
	if(memo.count(mp(m,cd)))return memo[mp(m,cd)];
	if(m==511)return memo[mp(m,cd)]=1;
	if(cd.empty())return memo[mp(m,cd)]=0;
	
	bool win=0;
	rep(i,cd.size()){
		vi nxt;
		int nm=m|cd[i];
		rep(j,cd.size())if(i!=j)nxt.pb(cd[j]&(~nm));
		sort(all(nxt));
		if(!rec(nm,nxt))win=1;
	}
	return memo[mp(m,cd)]=win;
}

class FiveHundredEleven {
	public:
	string theWinner(vector <int> cards) 
	{
		memo.clear();
		sort(all(cards));
		return rec(0,cards)?"Fox Ciel":"Toastman";
	}
};

方針2

メモリの数字に影響を与えないカードは全て同一視できる。
なのでメモリと、ターン数を覚えておくだけでメモ化ができる。

  • 「メモリの数字に影響を与えるカード」は、全てまだ使っていないカードで、
  • 「メモリの数字に影響を与えないカード」は(m枚とする)そのうち、
  • ターン数枚のカードが使ったカード
  • (m-ターン数)枚のカードがまだ使ってないカードである!

ソースコード

int n, dp[51][512], cd[50];
bool rec(int use, int bit){
	if(dp[use][bit]!=-1)return dp[use][bit];
	if(bit==511)return dp[use][bit]=1;
	if(use==n)return dp[use][bit]=0;
	
	bool win=0;
	int notchange=0;
	rep(i,n)if((cd[i]|bit)==bit)notchange++;
	if(notchange>use)win|=!rec(use+1,bit);
	
	rep(i,n)if((cd[i]|bit)!=bit){
		win|=!rec(use+1,bit|cd[i]);
	}
	return dp[use][bit]=win;
}
class FiveHundredEleven {
	public:
	string theWinner(vector <int> cards) 
	{
		n=cards.size();
		rep(i,n)cd[i]=cards[i];
		rep(i,n+1)rep(j,512)dp[i][j]=-1;
		
		return rec(0,0)?"Fox Ciel":"Toastman";
	}
};