TopCoder SRM 522 Div1 Easy RowAndCoins
問題
二人のプレイヤーが'A','B'からなる文字列に対して次のようなゲームを行う。
- コインの置かれていない連続する文字列の部分に対して、コインを置く
- ただし、全ての文字の上のコインが置かれる状態にしてはいけない
- コインが置けなくなったときに、残った文字が'A'なら先手の勝ち、'B'なら後手の勝ちである。
制約条件
文字列の長さ≦16
方針
メモ化再帰した。
O(1)の解法もある
ソースコード
int n; string cells; map<pi,bool> M; bool dfs(int flag, int turn){ if(M.count(mp(flag,turn)))return M[mp(flag,turn)]; bool &ret=M[mp(flag,turn)]; if(__builtin_popcount(flag)==n-1){ rep(i,n)if(!(flag>>i&1))return ret=(cells[i]=='A')^turn; } ret=0; rep(i,n)if(!(flag>>i&1)){ int j; for(j=i;j<n&&!(flag>>j&1);j++){ flag^=1<<j; if(__builtin_popcount(flag)<n&&!dfs(flag,1-turn))ret=1; } for(int k=i;k<j;k++) flag^=1<<k; if(ret)return ret; } return ret; } class RowAndCoins { public: string getWinner(string cells) { n=cells.size(); ::cells=cells; M.clear(); return dfs(0,0)?"Alice":"Bob"; } };