AtCoder ABC #383 (大和証券プログラミングコンテスト2024) : G - Bar Cover

これで、ブログ中のAtCoderの解説は1000記事目だね。
https://atcoder.jp/contests/abc383/tasks/abc383_g

問題

N要素の整数列Aと、整数Kが与えられる。

Aから、連続するK要素を重複せずi個選んだ時、その和を最大化したい。
i=1～floor(N/K)のそれぞれについて求めよ。

解法

あらかじめB[i]=A[i]+A[i+1]+...+A[i+K-1]とする数列を考えると、この問題はBから互いに(K-1)要素以上明けながらi要素選ぶ問題となる。
f(L,R,l,r,i) := B[L]...B[R]のうち、先頭l要素、末尾r要素を選べない場合、i要素選んだ時の最大値
とする。まずR=L+K-1とすると、B[L]...B[R]からは最大1要素しか選べない。
その状態のf(L,R,l,r,i)を埋めよう。
あとはSegTreeの要領で、隣接する区間の値f(L,M,*,*,*)とf(M,R,*,*,*)をマージしていく。
その際、f(L,R,l,r,i+1)-f(L,R,l,r,i)≧f(L,R,l,r,i+2)-f(L,R,l,r,i+1)なので、iについてマージソートの要領で貪欲に最大値を選んでいける。

int N,K;
int A[202020];
ll B[202020];
ll S[202020];

vector<ll> X[200010][5][5],Y[5][5],Z[5][5];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	int num=N/K;
	FOR(i,N) cin>>A[i];
	N-=K-1;
	FOR(i,N) FOR(j,K) B[i]+=A[i+j];
	
	for(i=0;i<N;i+=K) {
		FOR(x,K) FOR(y,K) {
			X[i/K][x][y]={0};
			ll ma=-1LL<<50;
			for(j=x;j+y<K&&i+j<N;j++) ma=max(ma,B[i+j]);
			if(ma!=-1LL<<50) X[i/K][x][y].push_back(ma);
		}
	}
	N=(N+K-1)/K;
	while(N>1) {
		for(i=0;i<N;i+=2) {
			if(i+1==N) {
				FOR(x,K) FOR(y,K) X[i/2][x][y]=X[i][x][y];
				continue;
			}
			FOR(x,K) FOR(y,K) {
				Y[x][y]=X[i][x][y];
				Z[x][y]=X[i+1][x][y];
				X[i/2][x][y].clear();
			}
			FOR(x,K) FOR(y,K) {
				FOR(j,K) {
					k=K-1-j;
					vector<ll> V;
					int a=0,b=0;
					while(a<Y[x][j].size()&&b<Z[k][y].size()) {
						V.push_back(Y[x][j][a]+Z[k][y][b]);
						if(a+1==Y[x][j].size()) b++;
						else if(b+1==Z[k][y].size()) a++;
						else if(Y[x][j][a+1]-Y[x][j][a]>=Z[k][y][b+1]-Z[k][y][b]) a++;
						else b++;
					}
					FOR(r,V.size()) {
						if(r==X[i/2][x][y].size()) X[i/2][x][y].push_back(V[r]);
						chmax(X[i/2][x][y][r],V[r]);
					}
				}
			}
			
		}
		N=(N+1)/2;
	}
	
	FOR(i,num) {
		ll ret=-1LL<<60;
		FOR(x,K) FOR(y,K) if(X[0][x][y].size()>i+1) ret=max(ret,X[0][x][y][i+1]);
		cout<<ret<<" ";
	}
	cout<<endl;
	
}

まとめ

もっと計算時間かかると思ったけど、意外に1秒かからなかったな。