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"; } };