SRM 534 div1 easy: EllysCheckers
解法
制約が小さいので脳筋 bitDP しましょう。
int n; int dp[1<<20]; int dfs(int state) { int& ret = dp[state]; if (ret >= 0) return ret; for (int i = 0; i < n-1; i++) { if ((state>>i)&1) { int next = i+1; if (next < n) { if (next == n-1 || ((state>>next)&1) == 0) { int nstate = state; nstate ^= 1<<i; nstate ^= 1<<next; if (!dfs(nstate)) return ret = 1; } } next = i+3; if (next < n) { if (next == n-1 || ((state>>next)&1) == 0) { int nstate = state; nstate ^= 1<<i; nstate ^= 1<<next; if (!dfs(nstate)) return ret = 1; } } } } return ret = 0; } class EllysCheckers { public: string getWinner(string board) { n = board.size(); int fs = 0; for (int i = 0; i < n-1; i++) { if (board[i] == 'o') fs |= 1<<i; } memset(dp, -1, sizeof(dp)); if (dfs(fs)) return "YES"; else return "NO"; } };