何も考えずにゲーム DP
毎ターン「実質的に取れる選択肢が二通りしかない」というパターン

という包畜を含む教育的問題。

問題概要

先手と後手は初期状態で $Z$ と $W$ と書かれたカードを持っている。 $N$ 枚の山札があってそれぞれ $a_1, a_2, \dots, a_N$ の数値が書かれている。交互に

残っている山札から添字が小さい順に好きな枚数のカードをとる (1 枚以上は必ずとる)
最後にとったカードのみを持ち、それ以外は捨てる

というのを山札が空になるまで繰り返す。最終盤面において

先手はカードの数値の差を最大化したい、
後手はカードの数値の差を最小化したい。

双方最善を尽くしたときの「カードの数値の差」はいくらになるか？

制約

$1 \le N \le 2000$

解法 1: 何も考えずに DP

ゲームのありうる局面は

すでに山札からとったカードの枚数
先手か後手か

のみである。よって状態数は $2N$ 程度と小さいので、何も考えずに DP することができる。

dp[ 山札からとった枚数 ][ 後手かどうか ] := その状態からスタートしたときの、最終的なカードの数値の差の最適値 (先手なら最大値、後手なら最小値)

としてあげて

先手番

すでに i 枚のカードがとられている状態を考える。このとき後手の持っているカードは Y = a[ i - 1 ] (i = 0 のときは W) なので、

すべての山札をとるなら、スコアは | Y - a[ N - 1 ] | なので chmax(dp[ i ][ 0 ], | Y - a[ N - 1 ] |
i < j として、chmax(dp[ i ][ 0 ], dp[ j ][ 1 ])

後手番

すでに i 枚のカードがとられている状態を考える。このとき先手の持っているカードは X = a[ i - 1 ]] (i = 0 のときは Z) なので、

すべての山札をとるなら、スコアは | X - a [ N - 1 ] | なので chmin(dp[ i ][ 1 ], | X - a[ N - 1 ] |
i < j として、chmin(dp[ i ][ 1 ], dp[ j ][ 0 ])

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;

int main() {
    long long N, Z, W; cin >> N >> Z >> W;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<vector<long long> > dp(N+1, vector<long long>(2));
    for (int i = N-1; i >= 0; --i) {
        // 先手番
        dp[i][0] = -INF; // 初期化
        long long Y = (i ? a[i-1] : W);
        chmax(dp[i][0], abs(Y - a[N-1]));
        for (int j = i+1; j < N; ++j) chmax(dp[i][0], dp[j][1]);

        // 後手番
        dp[i][1] = INF; // 初期化
        long long X = (i ? a[i-1] : Z);
        chmin(dp[i][1], abs(X - a[N-1]));
        for (int j = i+1; j < N; ++j) chmin(dp[i][1], dp[j][0]);
    }
    cout << dp[0][0] << endl;
}

解法 2: 実質的にとりうる手が二通り

先手と後手どちらにとっても、結局最後にとった手しか影響しない。それならモタモタしてないで、さっさといいものを選んだ方よい。蟻本の例題 Euclid's Game などもそんな構造の例題になっている。

どちらが手番になっても、a[N-1] を選ぶというのが強くて、相手に強制的に a[N] を選ばせることができる。そして先手が | a[N-1] - a[N] | より良いスコアをとりたくて中途半場に a[ (N-1) 未満 ] を選んでも相手に a[N-1] をとられて終わる。同じことが後手にも言える。

先手が一発で終わらせる場合：スコアは | a[N-1] - W | になる
それ以外の場合：スコアは | a[N-2] - a[N-1] | になる (N >= 2 のみ)

これらの大きい方が答えになる。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
    long long N, Z, W; cin >> N >> Z >> W;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    long long res = abs(W - a[N-1]);
    if (N > 1) chmax(res, abs(a[N-2] - a[N-1]));
    cout << res << endl;
}

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

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

AtCoder ABC 078 D - ABS (ARC 085 D) (青色, 500 点)

問題概要

制約

解法 1: 何も考えずに DP

先手番

後手番

解法 2: 実質的にとりうる手が二通り