SRM534 Div1 Easy

250
メモ化する。
この程度の問題を本番で間違うとか人権がない。

自分は if ( !bool ) の代わりに if ( bool^1 ) とすることがある。
!を使えば if ( int ) でも同じ目的で使えるけど、^1 はそんなことない。
思わず、(bit & (1 << n)) ^ 1 なんてやってしまった。正しくは、(bit & (1 << n)) ^ (1 << n) もしくは !(bit & (1 << n))
華麗に間違ったから反省

const int BIT = (1 << 20);
const int W = 0, L = 1;

int memo[BIT];

int rec(int bit, const int size)
{
  if (bit & (1 << (size - 1))) bit ^= 1 << (size - 1);
  if (memo[bit] != -1) return memo[bit];  
  int ret = L;

  for (int i = 0; i < size; ++i) {
    int a = 1 << i;
    int b = 1 << (i + 1);
    int c = 1 << (i + 2);
    int d = 1 << (i + 3);
    if (i + 3 < size) {
      if ((bit & a) && (bit & b) && (bit & c) && (bit & d)^d) {
        ret = min(ret, rec(bit ^ a ^ d, size) ^ 1);
      }
    }
    if (i + 1 < size) {
      if ((bit & a) && (bit & b)^b) {
        ret = min(ret, rec(bit ^ a ^ b, size) ^ 1);
      }
    }
  }
  
  return memo[bit] = ret;
}

class EllysCheckers {
public:
  string getWinner(string B) 
  {
    fill(memo, memo + BIT, -1);
    int bit = 0;
    for (int i = 0; i < B.size(); ++i) {
      bit = bit | ((B[i] == 'o') << i);
    }
    return rec(bit, B.size()) == W ? "YES" : "NO";
  }

};