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

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

問題へのリンク

問題概要

数列 \(a = a_1, a_2, \ldots, a_N \) がある。二人で以下の操作を交互に行う。

• a の先頭要素または末尾要素を取り除く。 取り除いた要素を x とすると、操作を行った人は x 点を得る。

先手の得点を X, 後手の得点を Y とする時、先手は X-Y を最大化しようとし、後手は X-Yを最小化しようとする。
最終的な X-Y の値は何か？

制約

• \(1 \leq N \leq 3000\)
• \(1 \leq a_i \leq 10^9\)

考え方

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

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

ゲームの終了状態(数列が全て取り除かれた時)から逆に考えて、ゲーム開始時点までの状態を探索していきます。

遷移の方法としては、まずどちらの手番なのかを考える必要があります。実は残り個数 (j-i) の時は、今までに取った数は N -(j-i) になるので、

• N – (j-i) が偶数のとき：先手の手番
• N – (j-i) が奇数のとき：後手の手番

になることが分かります。先手の時は最終スコアが増加し、後手の時は最終スコアが減少するようにしなければなりません。

数列の取り方としては、

• \(a_i\) を取る時
• \(a_j\) を取る時

の2種類があり、この2つの場合を考えてやれば良いです。

初期化

• dp[ i ][ i ] = 0

残り個数が 0個の時はどちらも得点が 0 なので、 X-Y も 0 になります。

更新

• N – (j-i) が偶数のとき：先手の手番
  • dp[ i ][ j ] = max(dp[ i ][ j – 1 ] + A[ j – 1 ], dp[ i + 1 ][ j ] + A[ i ]);
• N – (j-i) が奇数のとき：後手の手番
  • dp[ i ][ j ] = min(dp[ i ][ j – 1 ] – A[ j – 1 ], dp[ i + 1 ][ j ] – A[ i ]);

更新の順序には注意が必要です。既に更新が終わった部分を利用して、次の更新を行う必要があります。

メモ化再帰で実装したほうがやりやすいかもしれません。

C++での実装例

メモ化再帰

今回のように dp の更新を for 文で書きにくい場合は、メモ化再帰の方が実装しやすいです。

#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;

using ll = long long;
using ull = unsigned long long;
const ll INF = 1e18;

int N;
vector<vector<ll>> dp;
vector<ll> a;

ll rec(int l = 0, int r = N) {
    if (r == l) return 0;
    ll &ret = dp[l][r];
    if (ret != INF) return ret;

    if ((N - (r - l)) % 2 == 0) {  // 先手
        ret = max(a[l] + rec(l + 1, r), rec(l, r - 1) + a[r - 1]);
    } else {  // 後手
        ret = min(-a[l] + rec(l + 1, r), rec(l, r - 1) - a[r - 1]);
    }

    return ret;
}

int main() {
    cin >> N;
    a.assign(N, 0);
    dp.assign(N + 5, vector<ll>(N + 5, INF));
    for (int i = 0; i < N; i++) {
        cin >> a.at(i);
    }

    cout << rec() << endl;

    return 0;
}

dp で更新

dp配列の対角線に並行に更新しました。

#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;
ll dp[3005][3005];
int main() {
    cin >> N;
    vector<int> A(N + 1);
    REP(i, N) cin >> A.at(i + 1);

    FOR(s, 2, N + 2) {  // jのstart位置
        FOR(j, s, N + 2) {
            int i = j - s + 1;
            if ((N - (j - i)) % 2 == 0) {  // 先手
                dp[i][j] = max(dp[i][j - 1] + A[j - 1], dp[i + 1][j] + A[i]);
            } else {  // 後手
                dp[i][j] = min(dp[i][j - 1] - A[j - 1], dp[i + 1][j] - A[i]);
            }
        }
    }

    cout << dp[1][N + 1] << endl;

    return 0;
}