問題

問題概要

長さ $n$ の数列 $a$ が与えられる。この数列を使って、LさんとRさんの2人でゲームを行う。

ゲームはLさんのターンで始まる。まず、Lさんは数列の左端からスタートし、そこから1つか2つの値を数列から取り除きその合計を自分のスコアとすることが出来る。次にRさんのターンとなる。Rさんは数列の右端からスタートする。この時、その前の段階でLさんが数列から取った個数が $k$ 個である時に、Rさんは $k$ 個または $k+1$ 個の値を数列の右端から順に取ることが出来る。

以下、交互に繰り返す。パスは出来ない。数列の値が取り尽くされるか、これ以上選べない状況になってしまったらそこでゲームを終了する。

D = (Lさんの合計スコア) - (Rさんの合計スコア)とすると、LさんはDを最大化するように、RさんはDを最小化するように最適に行動する時、Dの値を求めよ。

$1 \le n \le 4000$
$-10^5 \le a_i \le 10^5$

アイデア

DPで解くことを考えてみる。すると、必要な情報は数列の左端 $l$ 、右端 $r$ 、直前のターンで相手が取った個数 $k$ 、今どちらのターンかの4つになると考えられる。

ここで、今Lさんのターンで、上のような状況でのDを $L_{l,r,k}$ 、Rさんのターンで同様の状況でのDを $R_{l,r,k}$ とすると、それぞれは次のような遷移で更新していくことが可能になる：

$L_{l,r,k} = max( R_{l+k,r,k} + \sum_{i=l}^{l+k-1} a_i , R_{l+k+1,r,k+1} + \sum_{i=l}^{l+k} a_i )$ $R_{l,r,k} = min( L_{l,r-k,k} - \sum_{i=r-k+1}^{r} a_i , L_{l,r-k-1,k+1} - \sum_{i=r-k}^{r} a_i )$

これらを計算することで答え $D = L_{1,n,1}$ となる。このDPの計算量は見た目上 $O(n^3)$ に見えるが、実際そうではないことを確かめる。

まず $k$ に注目すると、 $k$ に到達するために最低でも $1+2+ \cdots +k = \frac{k(k+1)}{2}$ 個の値が既に数列から取られている状況であることを考えると、 $\frac{k(k+1)}{2} \le n$ という条件が成り立ち、 $k$ は $\sqrt{2n}$ 以下となることが確定する。

更に、LさんとRさんが取る値の個数の差 $d(=(n-r)-(l-1))$ に注目する。最も差が大きくなるような状況は、一方が前者と同じだけ、もう片方が+1になるような選び方をし続けるような状況だが、これを考慮すると $|d| \le k$ となることが分かる。 $d$ の定義より、 $r = n-d-l+1$ となるので、上で触れたDPを $l,d,k$ の3つの変数の形に変えることによって、 $O(n^2)$ で実現することが可能になる。

このDPの計算量の落とし方はかなり面白かったし勉強になった。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int INF = 500000000;

int n,a[4001];

int suma[4001]={};
int sigma_a(int l, int r)
{
    return suma[r]-suma[l-1];
}

int dp[4001][180][90][2];
int dfs(int l, int d, int k, int turn)
{
    if(abs(dp[l][d+90][k][turn])!=INF) return dp[l][d+90][k][turn];

    int r = n-d-l+1;

    int ret;
    int nd;
    if(turn==0)
    {
        ret = -INF;

        nd = n-r-(l+k-1);
        if(l+k<=r+1) ret = max(ret, dfs(l+k,nd,k,1) + sigma_a(l,l+k-1));

        nd = n-r-(l+k+1-1);
        if(l+k+1<=r+1) ret = max(ret, dfs(l+k+1,nd,k+1,1) + sigma_a(l,l+k));
    }
    else
    {
        ret = INF;

        nd = n-(r-k)-(l-1);
        if(l<=r-k+1) ret = min(ret, dfs(l,nd,k,0) - sigma_a(r-k+1,r));

        nd = n-(r-k-1)-(l-1);
        if(l<=r-k-1+1) ret = min(ret, dfs(l,nd,k+1,0) - sigma_a(r-k,r));
    }

    if(abs(ret)==INF) ret=0;
    return dp[l][d+90][k][turn] = ret;
}

void init()
{
    rep(i,4001)rep(j,180)rep(k,90)
    {
        dp[i][j][k][0] = -INF;
        dp[i][j][k][1] = INF;
    }

    for(int i=1; i<=4000; ++i) suma[i] = suma[i-1]+a[i];
}

int main()
{
    scanf(" %d", &n);
    rep(i,n) scanf(" %d", &a[i+1]);

    init();
    printf("%d\n", dfs(1,0,1,0));
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

CF 738 F - Financiers Game

問題

問題概要

アイデア

実装(C++)