ABS [AtCoder Regular Contest 085 D]

https://beta.atcoder.jp/contests/arc085/tasks/arc085_b

解法

https://beta.atcoder.jp/contests/arc085/submissions/1760269

！！理屈分かってません！！
ゲーム系問題でよくあるメモ化ミニマックス法をやればいい。
　
f(id,turn,x,y) := 山札からid枚既に引いたときに、turnの番で、Xさんの手持ちがx, Yさんの手持ちがyである時のスコア
　
turn=0ならXさんで、遷移先によるスコアを最大化するように選択する。
turn=1ならYさんで、遷移先によるスコアを最小化するように選択する。
　
これを普通にやるとTLEするので、メモ化する。
この時、idとturnをキーとしてメモ化すればいい。
この解法で祈ると通る。

int N, Z, W, A[2010];
#define INF INT_MAX/2
//---------------------------------------------------------------------------------------------------
int memo[2010][2];
int f(int id, int turn, int x, int y) {
    if (id == N) return abs(x - y);
 
    if (0 <= memo[id][turn]) return memo[id][turn];
 
    if (turn == 0) {
        int ma = -1;
        rep(i, id, N) ma = max(ma, f(i + 1, 1 - turn, A[i], y));
        return memo[id][turn] = ma;
    } else {
        int mi = INF;
        rep(i, id, N) mi = min(mi, f(i + 1, 1 - turn, x, A[i]));
        return memo[id][turn] = mi;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Z >> W;
    rep(i, 0, N) cin >> A[i];
 
    rep(i, 0, N) rep(t, 0, 2) memo[i][t] = -1;
    cout << f(0, 0, Z, W) << endl;
}