mayoko’s diary

プロコンとかいろいろ。

SRM 493 div1 easy: StonesGame

SRM 400 番台の easy は簡単(ホントか)

解法

まず, 一回の白石の移動で目的の場所まで動かせたら Romeo の勝ちです。

そうでない場合は, Romeo は負けないように動かします。どんなふうに石を動かしても次に Strangelet が勝ってしまうなら, Strangelet の勝ちです。

以上のどちらでもない場合は, ある移動で白石が位置 x から 位置 y に移動した場合, 次の人は 位置 y から 位置 x に移動できるので, お互いににらみ合いが起きて引き分けになります。

class StonesGame {
public:
    string winner(int N, int M, int K, int L) {
        M--; L--;
        set<int> S;
        for (int i = 0; i < K; i++) {
            int l = M-K+1+i, r = M+i;
            if (l < 0 || r >= N) continue;
            int next = M-K+1+2*i;
            if (next == L) return "Romeo";
            S.insert(next);
        }
        int cnt = 0;
        for (int i = 0; i < K; i++) {
            int l = L-K+1+i, r = L+i;
            if (l < 0 || r >= N) continue;
            int next = L-K+1+2*i;
            if (S.find(next) != S.end()) cnt++;
        }
        if (cnt == S.size()) return "Strangelet";
        return "Draw";
    }
};