blue_jamのTopCoder日記

SRM 493 Div1 Easy

SRM, Practice | 21:23

概要

N個の石が1列にあって，M番目の石が白，他はすべて黒になっている．

2人のプレイヤーが交互にK個の連続した石を選んで，その順番を入れ替える．

先にL番目の位置に白い石を配置したほうが勝ち．

どちらのプレイヤーが勝つか求める．（いつまでたっても終わらない場合は引き分け）

解法

初手でLに移動させられたら，先手の勝ち．

2手目で確実にLに移動させられたら，後手の勝ち．

3手以上かかる場合は，相手と同じ動きをして，無限ループに落としこむことができるので，引き分け．

class StonesGame {
public:
    bool can(int N,int M, int K, int L){
        int num = max(L, M) - min(L, M) + 1;
        if(num % 2 != K % 2) return false;
        int t = (K - num) / 2;
        if(t < 0) return false;
        return min(M, L) - t  >= 0 && max(M, L) + t < N;
    }
    string winner(int N, int M, int K, int L) {
        bool win;
        M = M - 1; L = L - 1;
        if(can(N, M, K, L)) return "Romeo";
        win = true;
        for(int i=0;i+K<=N;++i){
            int next;
            if(i + K <= M)
                continue;
            if(M < i)
                continue;
            next = i + K - (M - i) - 1;
            win = win && can(N, next, K, L);
        }
        return win ? "Strangelet": "Draw";
    }
};