TDPC (Typical DP Contest) B - ゲーム

相手との得点差を最大化したいタイプのゲーム DP！

• 問題へのリンク

問題概要

2 つの山があります。

• 1 つ目の山には 個の物が積まれていて、上から順に価値は となっている
• 2 つ目の山には 個の物が積まれていて、上から順に価値は となっている

先手と後手は、交互に「いずれかの山を選び、その時点で一番上にある物をとる」ことを繰り返します。ただし、山が 1 つしか残っていない場合には、その山の一番上にある物をとります。

先手も後手も、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 になりますね！

今回の問題

今回の問題の場合、盤面の状態は

• 1 つ目の残山の上にある物の添字 (初期状態で )
• 2 つ目の残山の上にある物の添字 (初期状態で )

を用いて表せます。この状態の盤面を と表すことにします。

よって、次のような再帰関数で解けます。この再帰関数では、メモ化も実施しています。

また、盤面 の時点で 2 山に残っている物の価値の総和を sum としたとき、自分手番の得る得点と、相手手番の得る得点の和は sum となることに注意します。

// 盤面 (i, j) の状態からスタートする (sum = その盤面上にある物の価値の総和)
// その状態で手番であるプレイヤーの得られる得点の最大値を返す
int dfs(int i, int j, int sum, vector<vector<int>> &dp) {
    // メモ化済みならば、メモ化された値を返す
    if (dp[i][j] != -1) return dp[i][j];

    // 終端条件
    if (i == A && j == B) return 0;

    // 打てる手をすべて試す
    int res = 0;
    if (i < A) {
        // 1 つ目の山からとるとき
        res = max(res, sum - dfs(i+1, j, sum-a[i], dp));
    }
    if (j < B) {
        // 2 つ目の山からとるとき
        res = max(res, sum - dfs(i, j+1, sum-b[j], dp));
    }

    // メモ化しながら答えを返す
    return dp[i][j] = res;
}

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

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

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

コード

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

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

// 入力
int A, B;
vector<int> a, b;

// 盤面 (i, j) の状態からスタートする (sum = その盤面上にある物の価値の総和)
// その状態で手番であるプレイヤーの得られる得点の最大値を返す
int dfs(int i, int j, int sum, vector<vector<int>> &dp) {
    // メモ化済みならば、メモ化された値を返す
    if (dp[i][j] != -1) return dp[i][j];

    // 終端条件
    if (i == A && j == B) return 0;

    // 打てる手をすべて試す
    int res = 0;
    if (i < A) {
        // 1 つ目の山からとるとき
        res = max(res, sum - dfs(i+1, j, sum-a[i], dp));
    }
    if (j < B) {
        // 2 つ目の山からとるとき
        res = max(res, sum - dfs(i, j+1, sum-b[j], dp));
    }

    // メモ化しながら答えを返す
    return dp[i][j] = res;
}

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