いわゆる「相手との得点差を最大化したい」タイプのゲーム DP ですね！

問題へのリンク

問題概要

太郎君と次郎君が数列 $(a_{0}, a_{1}, \dots, a_{N-1})$ を使ってゲームをします。太郎君を先手として、交互に次の操作を行います。

数列の先頭要素または末尾要素を除去する
除去した値の分だけ得点が得られる

数列が空になった瞬間にゲームは終了します。

ゲーム終了時の太郎君の総得点を $X$ 、次郎君の総得点を $Y$ とします。太郎君は $X−Y$ を最大化しようとし、次郎君は $X−Y$ を最小化しようとします。

二人が最適に行動すると仮定したとき、 $X−Y$ を求めてください。

制約

$1 \le N \le 3000$

解法

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

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

qiita.com

さて、今回のゲームは、お互いに「自分の得点から相手の得点を引いた値」を最大化したい構造になっています。実際、今回の問題設定は、

太郎君は $X-Y$ を最大化したい
次郎君は $Y-X$ を最大化したい

というように考えることができます。

このようなゲームをゼロサムであると言います。ゼロサムゲームを解くためには、次のような再帰関数が有効です。

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

    // 打てる手をすべて試す
    int res = -INF;
    for (state2  : state から遷移できる局面全て) {
        // dfs(state2) によって、相手視点の得点が得られるので -1 倍する
        res = max(res, -dfs(state2) + (その手で得る利得));
    }
    return res;
}

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

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

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

今回の問題

今回の問題では、盤面の状態は、残っている数列の区間 $\lbrack l, r)$ によって表せます。これを盤面 $(l, r)$ と表すことにします。

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

// 盤面 (l, r) からスタートして、
// その状態で手番であるプレイヤー視点での相手との得点差の最大値を返す
long long dfs(int l, int r, vector<vector<long long>> &dp) {
    // メモ化済みならば、メモ化された値を返す
    if (dp[l][r] != -INF) return dp[l][r];

    // 終端条件
    if (l == r) return 0;

    // 打てる手をすべて試す
    long long res = -INF;
    res = max(res, -dfs(l+1, r, dp) + A[l]);  // 先頭を除去
    res = max(res, -dfs(l, r-1, dp) + A[r-1]);  // 末尾を除去
    
    // メモ化しながら答えを返す
    return dp[l][r] = res;
}

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

ありうる盤面の個数： $O(N^{2})$ 通り
各盤面で打てる手の個数： $O(1)$ 通り (高々 2 通り)

ですので、全体の計算量は $O(N^{2})$ となります。

コード

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<60;

// 入力
vector<long long> A;

// 盤面 (l, r) からスタートして、
// その状態で手番であるプレイヤー視点での相手との得点差の最大値を返す
long long dfs(int l, int r, vector<vector<long long>> &dp) {
    // メモ化済みならば、メモ化された値を返す
    if (dp[l][r] != -INF) return dp[l][r];
    
    // 終端条件
    if (l == r) return 0;
    
    // 打てる手をすべて試す
    long long res = -INF;
    res = max(res, -dfs(l+1, r, dp) + A[l]);  // 先頭を除去
    res = max(res, -dfs(l, r-1, dp) + A[r-1]);  // 末尾を除去
    
    // メモ化しながら答えを返す
    return dp[l][r] = res;
}

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

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

EDPC (Educational DP Contest) L - Deque

問題概要

制約

解法

今回の問題

コード