AtCoder ABC #303 (日鉄ソリューションズプログラミングコンテスト2023) : G - Bags Game

1分間に合わず…。
https://atcoder.jp/contests/abc303/tasks/abc303_g

問題

N個の袋が横一列に並んでおり、それぞれの袋iの中に入ったお金の金額X[i]が与えられる。
以下の2人ターン制のゲームを行う。
袋が残っている限りゲームは続き、各自自分のターンで以下の行動が取れる。

• 左右どちらかの端の袋を取る。
• A円ディーラーに払い、左右どちらかの端の袋を取ることをmin(B回,袋個数)分繰り返す。
• C円ディーラーに払い、左右どちらかの端の袋を取ることをmin(D回,袋個数)分繰り返す。

最終的な(先手の取得金額)-(後手の取得金額)を、先手は最大化、後手は最小化しようとする場合、この値はどうなるか。

解法

dp(L,R) := [L,R-1)番の袋が残った状態で自分の手番が来た時、(自分の取得金額)-(相手の取得金額)の最大値
とする。このテーブルを、区間長の短い順に埋めて行こう。

dp(L,R)を求める場合、R-L＞BかつA円払う場合を考える。
もし自分が[L',R')の袋を残して相手に手番を渡す場合、
dp(L,R) = sum(X[L]+...+X[R-1]) - sum(X[L']+....+X[R'-1]) - dp(L',R')
となる。これは(R'-L')の値別に(- sum(X[L']+....+X[R'-1]) - dp(L',R'))の最大値を求めるSegTreeを適宜作っていけばlog(N)で求められる。
よってこのテーブルを埋めるのにO(N^2logN)で済む。

ll N,A,B,C,D;
ll X[3030],S[3030];
ll dp[3030][3030];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-(1LL<<60);
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<ll,1<<13> st[3020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>C>>D;
	FOR(i,N) {
		cin>>X[i];
		S[i+1]=S[i]+X[i];
	}
	
	for(int len=1;len<=N;len++) {
		for(i=0;i+len<=N;i++) {
			dp[i][i+len]=-1LL<<60;
			chmax(dp[i][i+len],X[i+len-1]-dp[i][i+len-1]);
			chmax(dp[i][i+len],X[i]-dp[i+1][i+len]);
			if(len<=B) {
				chmax(dp[i][i+len],S[i+len]-S[i]-A);
			}
			else {
				chmax(dp[i][i+len],S[i+len]-S[i]-A+st[len-B].getval(i,i+B+1));
			}
			if(len<=D) {
				chmax(dp[i][i+len],S[i+len]-S[i]-C);
			}
			else {
				chmax(dp[i][i+len],S[i+len]-S[i]-C+st[len-D].getval(i,i+D+1));
			}
			st[len].update(i,-(S[i+len]-S[i])-dp[i][i+len]);
		}
	}
	
	
	cout<<dp[0][N]<<endl;
}

まとめ

変数の添え字ミスで間に合わなかった…。