WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM701 Div1 Easy "PartisanGame"

解法

りんごさんのソースコードを参考にしましたm(_ _)m

石取りゲームにありがちなdpをする。(現在の状態から遷移できる状態の中で、勝てるものがあれば勝ち というやつ)
だが、石の数が半端ないのでもう一工夫必要となる。

現在の状態から遷移できる状態はAlice側とBob側合わせても高々10パターンと少ないことを利用する。10パターンそれぞれ勝てる・勝てないの状態しかもっていないので、状態は2^10のバリエーションがあることになる。つまり、dpの状態は最大でも2^10の周期でループすることになる。よって、2^10までdpして、それ以上はループしていることを利用して算出するようにすればよい。

ソースコード

// dp[0][i]:= Aliceの番で石の数がi個あるとき、Aliceは勝てるか?
// dp[1][i]:= Bobの番で石の数がi個あるとき、Bobは勝てるか?
int dp[2][1234567];

class PartisanGame {
    public:
    string getWinner(int n, vector<int> a, vector<int> b) {
        // 2^10までdp
        for (int i = 0; i < 1234567; i++) {
            // Alice?
            dp[0][i] = false;
            for (int j = 0; j < a.size(); j++) {
                int x = a[j];
                if (x <= i && !dp[1][i - x]) dp[0][i] = true;
            }

            // Bob?
            dp[1][i] = false;
            for (int j = 0; j < b.size(); j++) {
                int x = b[j];
                if (x <= i && !dp[0][i - x]) dp[1][i] = true;
            }
        }

        // 周期を算出
        int q = 1050000; // 2^10以上!
        int p = q - 1;
        for (;; p--) {
            if (check(p, q)) break;
        }
        int cycle = p - q;

        // 答え算出
        if (n > p) n = (n - p) % cycle + p;
        return dp[0][n] ? "Alice" : "Bob";
    }

    // pとqは同じ状態か?
    bool check(int p, int q) {
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j < 5; j++) {
                if (dp[i][p + j] != dp[i][q + j]) return false;
            }
        }
        return true;
    }
};