Typical DP Contest B問題 : ゲーム

問題. ゲーム

2人で交互に行うゲームを考える．2つの山にはそれぞれ $A$ 個と $B$ 個のブロックが垂直に置かれており，上からそれぞれ $a_1, \ldots, a_A$ ， $b_1, \ldots, b_B$ の価値がある．交互にどちらかの山の上から1個のブロックを取る．互いに選択した価値の和が最大となるような最適な戦略を行ったとき，先手が得られる価値の和を求めよ．

制約： $1 \le A, B \le 1,000$ ，　 $1 \le a_i, b_j \le 1,000$

解法. 動的計画法（メモ化再帰）

説明のために，プレイヤーを区別して左と右と呼ぶことにします．左が先手のときの得られる価値の和の最大化を考えることにします．
$f(i, j)$ を山がそれぞれ $a_i, \ldots, a_A$ ， $b_j, \ldots, b_B$ としてゲームを始めたときに，左が得られる価値の和の最大値とします． $f(i, j)$ のときに左と右のどちらが先手なのかを考えるのですが，今回のゲームは交互に行うゲームなので， $i + j$ が偶数ならば左が先手となり， $i + j$ が奇数ならば右が先手となります．
次に， $f(i, j)$ のときの選択肢を考えます．選択肢は， $i \le A$ ならば $a_i$ を取るか， $j \le B$ ならば $b_j$ を取るかのどちらかになります．よって，左がその局面で先手のときは， $\max\{f(i + 1, j) + a_i, f(i, j + 1) + b_j\}$ が求める値となり，右がその局面で先手のときは， $\min\{f(i + 1, j), f(i, j + 1)\}$ が求める値となります．
上の再帰関数を計算して答え $f(0, 0)$ を求めると，計算時間は $O(2^{A + B})$ となります．このままでは TLE となるのですが， $f(i, j)$ の定義を思い出すと $f(i, j)$ は何度計算しても一意に定まります．したがって，メモ化再帰を行うと $O(A B)$ 時間で計算することができます．

計算時間： $O(A B)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

class Game {
public:
    Game(int _A, int _B) : A(_A), B(_B), a(_A), b(_B), dp(A + 1, vector<int>(B + 1, -1)) {}
    void Input() {
        for (auto &x : a) cin >> x;
        for (auto &x : b) cin >> x;
    }
    int Solve(const int i = 0, const int j = 0) {
        if (i == A && j == B) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        int &res = dp[i][j] = 0;
        bool snuke = ((i + j) % 2) == 0;
        if (i == A)
            res = Solve(i, j + 1) + ((snuke) ? b[j] : 0);
        else if (j == B)
            res = Solve(i + 1, j) + ((snuke) ? a[i] : 0);
        else
            res = snuke ? max(Solve(i, j + 1) + b[j], Solve(i + 1, j) + a[i])
                 : min(Solve(i, j + 1), Solve(i + 1, j));

        return res;
    }

private:
    int A, B;
    vector<int> a, b;
    vector<vector<int>> dp;
};

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int A, B;

    cin >> A >> B;
    Game g(A, B);
    g.Input();
    cout << g.Solve() << endl;

    return 0;
}

まとめ

2つの山ではなく $N$ 個の山としても同様にできますが， $N$ 人だとどうなるのでしょうね．たぶん同様にできると思うのですが．