Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Educational DP-L Deque】ゲームDPは何を最大化(最小化)するかを考える

L - Deque

問題

長さNの数列Aがあります。

先手後手の順で、前方か後方から数字を引き抜いていきます。

最終的に、先手の取った数字の和をX、後手のをYとすると、

先手はX-Yを最大化するように、後手はX-Yを最小化するように手を選びます。

スコアの最大値を求めなさい。

方針

先手についてdp1 = max { 一つとる + dp2 }, 後手についてdp2 = min { dp1 - 一つとる }のようなDPでも解けるのかも知れないですが、ピンと来ないので、違うアプローチでやってみます。

X+Yの和は一定なので、X-Yというのはconst - 2Y = const - 2 (const - X) = const + 2Xとなり、先手はXを最大化、後手はXを最小化する問題と見ることが出来ます。

dp[i][j] := Aの中の[i,j]を見てる時のXの最大値

として、これを簡明にメモ化再帰します。

実装

struct Rec {
    dp: Vec<Vec<Option<i64>>>,
    a: Vec<i64>,
}
impl Rec {
    fn solve(&mut self, left: usize, right: usize, turn: usize) -> i64 {
        if left == right { 
            if turn == 0 {
                return self.a[left];
            } else {
                return 0
            }
        }

        if let Some(x) = self.dp[left][right] {
            return x;
        }
        if turn == 0 {
            let newval = max(
                self.a[left] + self.solve(left+1, right, 1),
                self.a[right] + self.solve(left, right-1, 1)
            );
            self.dp[left][right] = Some(newval);
            newval
        }
        else if turn == 1 {
            let newval = min(
                self.solve(left+1, right, 0),
                self.solve(left, right-1, 0),
            );
            self.dp[left][right] = Some(newval);
            newval
        }
        else { unreachable!() }
    }
}
fn solve() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());

    input!{
        N:usize,
        a:[i64;N],
    }

    let mut sum_a = 0;
    for i in 0..N {
        sum_a += a[i];
    }

    let mut dp = dvec![None; N,N];
    let mut rec = Rec {
        dp: dp,
        a: a,
    };
    let x = rec.solve(0,N-1,0);
    let y = sum_a - x;

    println!("{}", x-y);
}