K – Stones 解説 (Educational DP Contest / DP まとめコンテスト)

2020年3月10日2020年9月2日AtCoder競プロ,ゲーム,二人零和有限確定完全情報ゲーム,後退解析,DP

問題へのリンク

問題概要

二人で以下のゲームを行う。先手と後手のどちらが勝つか？

• 以下の操作を交互に行う
  • A = \( a_1, a_2, \ldots, a_N\) の元 x を一つ選び、K 個の山から丁度 x 個取り除く
• 先に取り除けなくなったほうが負け

制約

• \(1 \leq N \leq 100\)
• \(1 \leq K \leq 10^5\)
• \(1 \leq a_1 < a_2 < \cdots < a_N \leq K\)

考え方

ゲームに関する問題です。後退解析という考え方が使えます。

後退解析とは、「ゲームの終了状態から出発して、ゲームの開始状態まで逆方向に解析していくこと」です。

具体的に考えましょう。残りが0個の時はその時の手番の人の負けです。ここから逆に考えると、

• 残りが \(a_1\) 個の時は \(a_1\) 取り除けば勝てる
• 残りが \(a_2\) 個の時は \(a_2\) 取り除けば勝てる
• 残りが \(a_3\) 個の時は \(a_3\) 取り除けば勝てる
• …
• 残りが \(a_N\) 個の時は \(a_N\) 取り除けば勝てる

となり、1つ逆方向に戻って勝ち負けを判定することができるのです。ここからどんどんと戻りながら考えていきますが、普通にやると N 個ずつ分岐していってしまい、計算量が膨大になってしまいます。

そこで、後退解析は以下のようにDPを使うことで高速に計算することができます。

初期化

• dp[ i ] := false

更新

配る dp で考えると以下のようになります。

• dp[ i + a[ j ]] = dp[ i ] が false なら true

もらう dp で考えると以下の通りです。

• dp[ i ] = dp[ i – a[ j ] ] に false が存在するなら true

意味的には後者のほうが分かりやすいかもしれません。相手が負けるような遷移先が存在するなら、そのように遷移するのが最善手です。

実装例

#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

int N, K;
bool dp[200005];
int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);

    cin >> N >> K;
    vector<int> A(N);
    REP(i, N) cin >> A.at(i);

    REP(i, K) {
        REP(j, N) {
            if (!dp[i]) dp[i + A[j]] = true; // 配るdp
        }
    }
    if (dp[K]) {
        cout << "First" << endl;
    } else {
        cout << "Second" << endl;
    }

    return 0;
}