AtCoder ABC #426 : G - Range Knapsack Query

開始が遅かったこともあって、全完間に合わず…。
https://atcoder.jp/contests/abc426/tasks/abc426_g

問題

i個目のアイテムの重さはW[i]、価値はV[i]とする。
以下のクエリに順次答えよ。

• 整数L,R,Cが与えられる。L～R番目のアイテムに対し、重さC以下で得られる価値の総和の最大値を求めよ。

解法

dfs(L',R') := 区間[L',R')に包含される区間に対し、M'=(L'+R')/2とした時、前半分と後ろ半分を1個以上ずつ含むクエリを処理することを考える。
上記に該当しないクエリは、dfs(L',M')かdfs(M',R')のいずれかで再帰的に処理をしていく。

この時、M'を末尾とするsuffixと、M'を先頭とするprefixにおけるナップサック問題のDPの結果を保持しよう。
もしクエリに対し、区間[L,M']で重さC'以下の範囲での価値の最大値を求めた場合、[M',R]では重さC-C'以下の範囲で価値の最大値を求めて足せばよい。
そのため、C'を総当たりしよう。

int N,Q;
int W[40202],V[40202];
ll dp[40202][512];
int L[202020],R[202020],C[202020];
ll ret[202020];
void dfs(int CL,int CR,vector<int> cand) {
	if(CL+1==CR) {
		FORR(c,cand) {
			if(W[CL]<=C[c]) ret[c]=V[CL];
		}
		return;
	}
	int CM=(CL+CR)/2;
	int i,j,x,y;
	FOR(x,501) {
		dp[CM-1][x]=0;
		dp[CM][x]=0;
	}
	for(x=W[CM-1];x<=500;x++) dp[CM-1][x]=V[CM-1];
	for(x=W[CM];x<=500;x++) dp[CM][x]=V[CM];
	for(x=CM-2;x>=CL;x--) {
		FOR(y,501) {
			dp[x][y]=dp[x+1][y];
			if(y>=W[x]) dp[x][y]=max(dp[x][y],dp[x+1][y-W[x]]+V[x]);
		}
		FOR(y,501) dp[x][y+1]=max(dp[x][y+1],dp[x][y]);
	}
	for(x=CM+1;x<CR;x++) {
		FOR(y,501) {
			dp[x][y]=dp[x-1][y];
			if(y>=W[x]) dp[x][y]=max(dp[x][y],dp[x-1][y-W[x]]+V[x]);
		}
		FOR(y,501) dp[x][y+1]=max(dp[x][y+1],dp[x][y]);
	}
	
	
	vector<int> C1,C2;
	FORR(c,cand) {
		if(R[c]<=CM) C1.push_back(c);
		else if(CM<=L[c]) C2.push_back(c);
		else {
			FOR(x,C[c]+1) ret[c]=max(ret[c],dp[L[c]][x]+dp[R[c]-1][C[c]-x]);
		}
	}
	dfs(CL,CM,C1);
	dfs(CM,CR,C2);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>W[i]>>V[i];
	}
	cin>>Q;
	vector<int> cand;
	FOR(i,Q) {
		cin>>L[i]>>R[i]>>C[i];
		L[i]--;
		cand.push_back(i);
	}
	dfs(0,1<<15,cand);
	FOR(i,Q) cout<<ret[i]<<endl;
	
}

まとめ

区間を分割するの、思いついたものの時間が足りなかった…。