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