AtCoder ABC 270 D - Stones (水色, 400 点)

いわゆる「得点差を最大化したい」というゲーム DP！！

• 問題へのリンク

問題概要

個の石が積まれた山を使って石取りゲームをします。先手と後手は交互に次の操作を行います。

• 個のいずれかの個数の石を取り除きます
• ただし、 が残っている石の個数よりも小さいときは、 個の石を取り除くことはできません

山から石がなくなったとき、ゲームは終了します。

2 人がともに、ゲーム終了までに自分が取り除いた石の個数を最大化しようとするとき、先手は何個の石を取り除くことができますか？

制約

• 
• 
• 

解法

いわゆる「ゲームを DP で解く」系の問題ですね！

そのタイプの問題にまったく馴染みのない方は、次の記事を読んでみてください。

qiita.com

さて、解きたいゲームにおいて、特に自分の得点も最大化したい場合には、次のような再帰関数を組んで解ける場合が多いです。

なお、局面 state において、先手の得る得点と、後手の得る得点の和が定数 sum であるとします (多くのゲームでは sum = 0 となります)。

// 盤面の状態が state である状態からスタートして、
// その状態で手番であるプレイヤーの得られる得点の最大値を返す
int dfs(State state) {
    // 終端条件
    if (state が終局である) return (終局に応じた得点);

    // 打てる手をすべて試す
    int res = -INF;
    for (state2  : state から遷移できる局面全て) {
        // dfs(state2) によって、相手視点の得点が得られる
        // これを sum から引いた値を用いて `res` を更新する
        res = max(res, sum - dfs(state2));
    }
    return res;
}

なお、このような形式の再帰関数を用いたゲーム探索は、ミニマックス法や、ネガマックス法などと呼ばれます。

競プロでは、この再帰関数をこのまま実装するだけだと TLE になることが多いです。それは、同一局面を何度も何度も探索し得ることが原因です。

そこで、メモ化しましょう。そうすると、いわゆるメモ化再帰と呼ばれる DP になりますね！

今回の問題

今回の問題では、「盤面の状態」は、残っている石の個数 で表せます。上記の再帰関数の細部を詰めて、メモ化することで AC できます。たとえば、下のコード例にように実装できます。

ここで、石の個数が 個である盤面から出発して、その手番の得る得点 (石の個数) と、相手手番の得る得点 (石の個数) の和は となることに注意します。

最後に計算量を見積りましょう。

• ありうる盤面の個数： 通り
• 各盤面で打てる手の個数： 通り

ですので、全体の計算量は となります。

コード

#include <bits/stdc++.h>
using namespace std;

// chmax
template<class T> void chmax(T& a, T b) { if (a < b) a = b; }

// 入力
int N, K;
vector<int> A;

// 盤面の状態が state である状態からスタートして、
// その状態で手番であるプレイヤーの得られる得点の最大値を返す
int dfs(int n, vector<int> &dp) {
    // すでに求まっている場合
    if (dp[n] != -1) return dp[n];
    
    // 終端条件
    if (n == 0) return 0;
    
    // 打てる手をすべて試す
    int res = 0;
    for (auto a : A) {
        if (a > n) break;
        
        // dfs(n-a) によって、相手視点の得点が得られるので、これを n から引く
        chmax(res, n - dfs(n-a, dp));
    }
    
    // メモ化して返す
    return dp[n] = res;
}

int main() {
    cin >> N >> K;
    A.resize(K);
    for (int i = 0; i < K; ++i) cin >> A[i];
    
    // メモ化再帰
    vector<int> dp(N+1, -1);
    cout << dfs(N, dp) << endl;
}