読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

CF 738 F - Financiers Game

問題

Problem - F - Codeforces

問題概要

長さ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;
}