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