キーエンス プログラミング コンテスト 2021 : E - Greedy Ant

本番ちょっと手間取ったけどどうにか解いてるね。
https://atcoder.jp/contests/keyence2021/tasks/keyence2021_e

問題

N個の飴を用いて、人間と蟻で対戦ゲームを行う。
各飴は左右1列に並んでおり、それぞれのおいしさが与えられる。
蟻はある位置にいる。

人間と蟻は交互に手番が来るが、人間は残った飴から任意の1つ、蟻は現在位置から左右最寄りの飴のいずれかを食べるとする。
両者自身の食べる飴のおいしさの和を最大化しようとするとき、蟻の各初期位置において、人間の食べる飴のおいしさの和の最大値を答えよ。

解法

人間は飛び飛びに飴を食べることができるのが厄介。
そこで、これを言い換え、人間は飛び飛びに飴を食べるのではなく、蟻と同様に、蟻の現在位置の左右いずれかを食べるものとする。
ただし、飛び飛びに食べることを再現するため、人間は「今食べるのを保留して、今後1回任意のタイミングで割り込んで飴を食べる権利を手に入れられる」と言い換えよう。
そうするとこの問題は以下のように置き換えられる。
f(L,R,C) := 今区間蟻の最寄りの左右の飴がL,Rで、人間の保留回数が1であるとき、人間が食べる飴のおいしさの総和の最大値
とすると、解は各xについてf(x,x+1,1)となる。
この遷移は以下のO(1)通りとなる。

• 人間が保留し、蟻が左右いずれかの飴を食べる
• 人間が保留分を使って、左右いずれかの飴を食べる

状態がO(N^3)通りなので、全体でO(N^3)で解ける。

int N,A[404];
int dp[404][404][404];

int hoge(int L,int R,int C) {
	L=max(0,L);
	R=min(N+1,R);
	if(dp[L][R][C]>=0) return dp[L][R][C];
	if(L==0&&R==N+1) return 0;
	
	int ret=0;
	
	if(C) {
		if(L>0) ret=max(ret,A[L]+hoge(L-1,R,C-1));
		if(R<N+1) ret=max(ret,A[R]+hoge(L,R+1,C-1));
	}
	
	
	if(L==0) ret=max(ret,hoge(L,R+1,C+1));
	else if(R==N+1) ret=max(ret,hoge(L-1,R,C+1));
	else {
		if(A[L]>A[R]) {
			ret=max(ret,hoge(L-1,R,C+1));
		}
		else{
			ret=max(ret,hoge(L,R+1,C+1));
		}
	}
	
	return dp[L][R][C]=ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(dp);
	cin>>N;
	FOR(i,N) cin>>A[i+1];
	
	FOR(i,N+1) {
		cout<<hoge(i,i+1,1)<<endl;
	}
	
}

まとめ

これは気が付くと気持ちの良い問題。