CF 738 F - Financiers Game
問題
問題概要
長さの数列が与えられる。この数列を使って、LさんとRさんの2人でゲームを行う。
ゲームはLさんのターンで始まる。まず、Lさんは数列の左端からスタートし、そこから1つか2つの値を数列から取り除きその合計を自分のスコアとすることが出来る。次にRさんのターンとなる。Rさんは数列の右端からスタートする。この時、その前の段階でLさんが数列から取った個数が個である時に、Rさんは個または個の値を数列の右端から順に取ることが出来る。
以下、交互に繰り返す。パスは出来ない。数列の値が取り尽くされるか、これ以上選べない状況になってしまったらそこでゲームを終了する。
D = (Lさんの合計スコア) - (Rさんの合計スコア)
とすると、LさんはDを最大化するように、RさんはDを最小化するように最適に行動する時、Dの値を求めよ。
アイデア
DPで解くことを考えてみる。すると、必要な情報は数列の左端、右端、直前のターンで相手が取った個数、今どちらのターンかの4つになると考えられる。
ここで、今Lさんのターンで、上のような状況でのDを、Rさんのターンで同様の状況でのDをとすると、それぞれは次のような遷移で更新していくことが可能になる:
これらを計算することで答えとなる。このDPの計算量は見た目上に見えるが、実際そうではないことを確かめる。
まずに注目すると、に到達するために最低でも個の値が既に数列から取られている状況であることを考えると、という条件が成り立ち、は以下となることが確定する。
更に、LさんとRさんが取る値の個数の差に注目する。最も差が大きくなるような状況は、一方が前者と同じだけ、もう片方が+1になるような選び方をし続けるような状況だが、これを考慮するととなることが分かる。の定義より、となるので、上で触れたDPをの3つの変数の形に変えることによって、で実現することが可能になる。
この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; }