mayoko’s diary

プロコンとかいろいろ。

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