Codeforces #775 : Div1 D. Serious Business

入出力量が多いな…。
https://codeforces.com/contest/1648/problem/D

問題

3*Nのグリッドがあり、各セルには整数値が設定されている。
ここで、左上マスから右または下の隣接マスをたどり、右下マスに移動することを考える。
この時、得られるスコアは通過したマスの設定値の総和である。

1行目と3行目の各セルは初期状態で移動可能であり、2行目は移動不可能である。
ここでQ個の提案が与えられる。
各提案は、2行目のL列目～R列目を移動可能とする代わりに、コストをK支払うというものである。

提案のうち任意個数を受け入れられる場合、スコアから総コストを引いた値の最大値を求めよ。

解法

s(i) := 1行目の先頭i列目までの設定値の総和から、2行目の先頭(i-1)列目までの設定値の総和を引いたもの
f(j) := 3行目のj～N列目までの設定値の総和に、2行目の先頭j列目までの設定値の総和を加えたもの
cost(i,j) := 2行目をi列目～j列目まで移動可能とするのに支払うコストの最小値

とすると、i列目で1行目から2行目、j列目で2行目から3行目に縦移動するとして、s(i)+f(j)-cost(i,j)を最大化する問題となる。
dp(j) := s(i)-cost(i,j)の最大値
とすると、dp(j)+f(j)の最大値を求めればよくなる。
dp(j)は、jを右端とする提案に対し順に区間最大値を取るSegTreeを更新していけばよい。

int N,Q;
int A[3][505050];
ll S[3][505050];

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]);
	}
};

template<class V,int NV> class SegTree_2 {
public:
	vector<V> A,B,C;
	static V const def=-(1LL<<60);
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_2(){A=B=C=vector<V>(NV*2,def);};
	
	pair<pair<ll,ll>,ll> getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return {{def,def},def};
		if(x<=l && r<=y) return {{A[k],B[k]},C[k]};
		auto a=getval(x,y,l,(l+r)/2,k*2);
		auto b=getval(x,y,(l+r)/2,r,k*2+1);
		ll s=max(a.first.first,b.first.first);
		ll t=max(a.first.second,b.first.second);
		ll u=max({a.second,b.second,a.first.first+b.first.second});
		return {{s,t},u};
	}
	void update(int entry, ll a,ll b) {
		entry += NV;
		A[entry]=a;
		B[entry]=b;
		C[entry]=a+b;
		while(entry>1) {
			entry>>=1;
			A[entry]=max(A[entry*2],A[entry*2+1]);
			B[entry]=max(B[entry*2],B[entry*2+1]);
			C[entry]=max({C[entry*2],C[entry*2+1],A[entry*2]+B[entry*2+1]});
		}
	}
};
SegTree_1<ll,1<<19> Sst;
SegTree_2<ll,1<<19> Fst;
ll ret=-1LL<<60;

vector<int> Rev[505050];
int L[505050],R[505050],K[505050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	FOR(y,3) {
		FOR(x,N) {
			scanf("%d",&A[y][x]);
			S[y][x+1]=S[y][x]+A[y][x];
		}
	}
	FOR(i,N) {
		Sst.update(i+1,S[0][i+1]-S[1][i]);
	}
	FOR(i,Q) {
		scanf("%d%d%d",&L[i],&R[i],&K[i]);
		Rev[R[i]].push_back(i);
	}
	for(i=1;i<=N;i++) {
		FORR(r,Rev[i]) {
			ll v=Sst.getval(L[r],R[r]+1)-K[r];
			Sst.update(i+1,v);
		}
	}
	for(i=1;i<=N;i++) {
		ll a=Sst.getval(i,i+1);
		ll b=S[1][i]+S[2][N]-S[2][i-1];
		Fst.update(i,a,b);
	}
	
	FOR(i,Q) {
		auto a=Fst.getval(L[i],R[i]+1);
		ret=max(ret,a.second-K[i]);
	}
	
	cout<<ret<<endl;
	
}

まとめ

考察するとシンプルなSegTreeの問題になるタイプの問題、なかなか難しい。