kmjp's blog

競技プログラミング参加記です

AtCoder ARC #066 : F - Contest with Drinks Hard

ARC

これ系の分割統治苦手。
http://arc066.contest.atcoder.jp/tasks/arc066_d

問題

N要素の数列A[i]がある。
ここから数列の要素をいくつか選択したとする。

その時のスコアは、選択した連続要素群A[L...R]に対し、(R-L)*(R-L+1)/2 - sum(A[L...R])の和をとったものである。

ここでQ個のクエリが与えられる。
各クエリqは2値(P[q],X[q])であらわされ、A[i]のうち1要素を書き換えA[P[q]]=X[q]にする場合を意味する。
各クエリに対し、適用後のスコアの最大値を求めよ。
(各クエリによる要素の書き換え結果は、他のクエリ処理時には残らない)

解法

前処理として、各要素に関しそれぞれ含む場合と含まない場合のスコアの最大値を求めよう。
そうすれば、各クエリに対しては要素P[q]を含む場合のスコアがA[i]-X[q]だけ減った場合について、要素P[q]を含む場合と含まない場合の大きい方のスコアを答えればよいことになる。

まず各要素を含まないケースを考える。下記を考える。
f(i) := A[0..i]までの要素のうち最適な選択により得られる最大スコア
sum(i) := A[0..i]の総和
するとA[j..i]を連続して選択していた場合を考えると f(i) = max(f(i-1), max_{j \lt i}(f(j-1) + (i-j)*(i-j+1)/2 - (sum(i)-sum(j)))とおける。
右側のmaxは式変形すると (j*i + f(j-1) + j*(j-1)/2 + sum(j)) + i*(i+1)/2 - sum(i)となり前半部はiの一次式となるのでConvexHullTrickで最大値を求められる。

同様に、g(j) := A[j..(N-1)]までの要素のうち最適な選択により得られる最大スコア　を求める。
するとA[i]を含まない場合の最大スコアはf(i-1)+g(i+1)で求められるようになった。

次はA[i]を含む場合の最大スコアである。
今区間[L..R]を考えるとき、中央のM=(L+R)/2とiの両方を含むケースの最大スコアを考えよう。

i＞Mの場合、[M..i]を含む最大スコアは max_{j \lt M}(f(j-1) + (i-j)*(i-j+1)/2 - (sum(i)-sum(j))) + g(i+1)で求められる。
i＜Mの場合も似たような式変形で求められる。
以後は、それぞれMを含まない領域のみを考えればよい。よって区間[L..(M-1)]および[(M+1)..R]について同様に再帰的に処理していけばよい。

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	int cmptype=1; // 0-min 1-max
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { // max or min
		return cmptype^((B.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-B.first));
	}
	void add(V a, V b) { // add ax+b
		Q.push_front({a,b});
		while(Q.size()>=3 && !dodo(Q[0],Q[1],Q[2]))
			Q[1]=Q[0], Q.pop_front();
	}
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			((cmptype^((calc(Q[M],x)>=calc(Q[M+1],x))))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};


int N;
ll T[303030],LS[303030],RS[303030];
int M;
ConvexHull<ll> LC, RC;
ll LD[303030],RD[303030],inc[303030],ninc[303030];
ll tmemo[303030];

void dfs(int LL,int RR) {
	if(RR-LL<=2) return;
	int MM=(LL+RR)/2;
	
	ConvexHull<ll> TLC, TRC;
	TLC.add(0,0);
	TRC.add(0,0);
	int i,j;
	for(i=LL;i<RR;i++) {
		if(i<MM) TLC.add(-(i+1), 1LL*i*(i+1)/2 + LD[i+1] + LS[i+1]);
		else tmemo[i]=TLC.query(i+1) + 1LL*(i+1)*(i+2)/2 - LS[i+1]+RD[N-1-i];
	}
	for(j=RR-1;j>=LL;j--) {
		i=N-1-j;
		if(j>=MM) TRC.add(-(i+1), 1LL*i*(i+1)/2 + RD[i+1] + RS[i+1]);
		else tmemo[j]=TRC.query(i+1) + 1LL*(i+1)*(i+2)/2 - RS[i+1]+LD[j];
	}
	
	ll ma=-1LL<<60;
	for(i=RR-1;i>=MM;i--){
		ma=max(ma,tmemo[i]);
		inc[i]=max(inc[i],ma);
	}
	ma=-1LL<<60;
	for(i=LL;i<MM;i++){
		ma=max(ma,tmemo[i]);
		inc[i]=max(inc[i],ma);
	}
	
	dfs(LL,MM);
	dfs(MM,RR);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i];
	
	LC.add(0,0);
	RC.add(0,0);
	FOR(i,N) {
		LS[i+1]=LS[i]+T[i];
		LD[i+1]=max(LD[i], LC.query(i+1) + 1LL*(i+1)*(i+2)/2 - LS[i+1]);
		LC.add(-(i+1), 1LL*i*(i+1)/2 + LD[i+1] + LS[i+1]);
		
		RS[i+1]=RS[i]+T[N-1-i];
		RD[i+1]=max(RD[i], RC.query(i+1) + 1LL*(i+1)*(i+2)/2 - RS[i+1]);
		RC.add(-(i+1), 1LL*i*(i+1)/2 + RD[i+1] + RS[i+1]);
	}
	FOR(i,N) {
		ninc[i]=LD[i]+RD[N-1-i];
		inc[i]=1-T[i];
	}
	dfs(0,N);
	
	
	cin>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--;
		cout<<max(ninc[x], inc[x] + T[x] - y)<<endl;
	}
	
}

まとめ

解ける気しないなぁ。