SRM 534 Div2 Medium EllysCheckers

一発では解けなかった.要復習

問題

checkerがあり,2つの操作を自分と相手で交互に行う.もし自分のターンで操作が行えなかったら負け.
操作1.i番目にcheckerがあり,i+1番目が空ならi+1番目にチェッカーを移動
操作2.i, i+1, i+2にチェッカーがあり,i+3番目が空ならi番目のチェッカーをi+3番目に移動(全体を右に移動するとも取れる)
また一番右端にcheckerが来たなら即座に削除される

解答

入力が20個なので全部のやり方を試しても大丈夫.もちろんメモ化はするが.
現在の状態をbit列で表現し,既に計算した状態を配列で保存.可能な移動を全部探索する.

const int maxbit = 20;
bool memo[1<<maxbit];
bool visited[1<<maxbit];
class EllysCheckers
{
public:
  int n;
  bool calc(int B){
    if (visited[B]) return memo[B];
    visited[B] = true;
    int i;
    bool res = false;
    for(i = 0; i < n-1; i++) if (((B>>i) & 1) && !(B>>(i+1) & 1)){
        int newB = B | (1<<(i+1));
        newB &= ~(1<<i);
        newB &= ~(1<<(n-1));
        res |= !calc(newB);
      }
    for(i = 0; i < n-3; i++) if (((B>>i) & 1) && (B>>(i+1) & 1) && (B>>(i+2) & 1) && !(B>>(i+3) & 1)){
        int newB = B | (1<<(i+3));
        newB &= ~(1<<i);
        newB &= ~(1<<(n-1));
        res |= !calc(newB);
      }
    memo[B] = res;
    return res;
  }
  string getWinner(string board)
    {
      n = board.size();
      fill(memo, memo+(1<<maxbit), false);
      fill(visited, visited+(1<<maxbit), false);
      int B = 0;
      for(int i = 0; i < n-1; i++) if (board[i] == 'o') B |= (1 << i);
      if (calc(B)) return "YES";
      return "NO";
    }
};