Codeforces ECR #059 : G. Vasya and Maximum Profit

Fよりずっと簡単。
http://codeforces.com/contest/1107/problem/G

問題

N要素の昇順列D[i]およびコスト列C[i]が与えられる。
このうちある区間[L..R]を抜き出すことを考える。
その時得られるスコアは、以下のとおりである。

• 区間中要素1個あたりAスコアが加算される
• 要素iを含むとコストC[i]が減算される
• 抜き出した区間のうち隣接要素間の差分の２乗((D[i]-D[i+1)^2)の最大値を引く

最適な位置を抜き出したとき、スコアの最大値を求めよ。

解法

まず、区間長が1の場合は先に総当たりしておく。

要素を含むごとに得られるスコアE[i]=A-C[i]とする。
先にE[i]を左右方向に累積和をとっておき、さらにそれぞれ区間内の最大値を取れるようSegTreeを構築しておこう。

スコア計算の３つ目の要素は、最大値で決まる要素である。
よって、隣接要素の差の大きい順に処理することを考える。
処理済みの隣接区間は、以後跨げないものとする。

今D[i],D[i+1]間が処理対象の隣接要素とする。
あとは、先ほどの左右方向の累積和の最大値を取るSegTreeを用いて、左側および右側に区間を伸ばし、スコアの最大化を目指そう。
当然、処理済みの隣接要素間は含められないので、それらをまたがない範囲でSegTreeを探索する。

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<<20> stL,stR;
int N,A;
ll D[303030],C[303030];
ll LC[303030],RC[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A;
	ll ret=0;
	FOR(i,N) {
		cin>>D[i+1]>>C[i+1];
		C[i+1]=A-C[i+1];
		ret=max(ret,C[i+1]);
		LC[i+1]=LC[i]+C[i+1];
	}
	set<int> NG;
	NG.insert(1);
	NG.insert(N+1);
	for(i=N;i>=1;i--) {
		RC[i]=RC[i+1]+C[i];
		stL.update(i,LC[i]);
		stR.update(i,RC[i]);
	}
	priority_queue<pair<ll,int>> PQ;
	for(i=2;i<=N;i++) PQ.push({(D[i]-D[i-1])*(D[i]-D[i-1]),i});
	
	while(PQ.size()) {
		auto p=PQ.top();
		PQ.pop();
		
		x=p.second;
		auto it=NG.lower_bound(p.second);
		int R=*it;
		it--;
		int L=*it;
		NG.insert(x);
		
		ret=max(ret,stL.getval(x,R)-LC[x-1]+stR.getval(L,x)-RC[x]-p.first);
	}
	cout<<ret<<endl;
	
}

まとめ

Fはハンガリアン法の理解含め5日もかかったのに…。