kmjp's blog

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

CSAcademy Round #86 : E. Growing Segment

こういうデータ構造苦手。
https://csacademy.com/contest/round-86/task/growing-segment/

問題

1次元の座標系において、非負整数Lに対し以下を考える。
初期状態で[0,L]の間に線分が配置されている。
ここでN個の座標が指定される。
そこで、この線分を(長さを変えず)座標軸上を左右に動かし、指定された座標を指定された順で線分中に含むようにする。
その際線分の移動量を最小にすることを考える。

LがQ通り与えられるので、それぞれ移動量を答えよ。

解法

まず与えられた座標を整理しよう。
3個以上連続で増加したり減少したりする座標列において、中央部は考慮する必要がないのでそれらは最初に取り除こう。
そうすると到達すべき座標は増加と減少を交互に繰り返す形となる。
また、線分は左右に交互に移動を行うことになる。

L=0の場合、解は連続する頂点の座標の差の総和となる。
ここでLが1増えると、次の座標に移動する際の移動距離が1減るので、全体では(頂点数-1)だけ減少する。
ただし、Lが増え頂点間の距離以上になると、もはやそれらの頂点間で線分を移動する必要はなくなるので、到達すべき頂点は減らすことができる。

こう考えるとLは小さい順に徐々に考えていくのがよい。
よってクエリはLの小さい順に処理して行こう。
その際、残された到達すべき頂点列と、その間の距離をset等で管理していく。
基本的には「Lが1増えると、次の座標に移動する際の移動距離が1減るので、全体では(頂点数-1)だけ減少する。」に従い総移動量を更新していき、頂点間の距離がL以下になるようなケースに遭遇したら頂点をいくつか取り除こう。

以下1例を示す。
今到達すべき頂点が…→L1→R1→L2→R2→L3→R3→…のようになっているとする。
頂点vの座標をX[v]とすると、X[L1]<X[R1]>X[L2]<X[R2]>X[L3]<X[R3]…となる。

ここでX[R2]-X[L2]がL以下である場合を考える。
線分の左端がX[L2]に到達した時点で右端はX[R2]以上になるので、まず頂点列からR2を取り除こう。
この後、X[L2]とX[L3]の大小関係により座標の小さい方を消す。
その結果、到達すべき頂点がL1→R1→L3→R3→になるケースとL1→R1→L2→R3→になるケースがあるので、それぞれR1・L2・L3から次の頂点までの距離を更新しておこう。

int N,Q;
vector<int> X;
ll ret[101010];
vector<pair<int,int>> VV;

set<int> S;
set<pair<int,int>> cand;
int D[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	X.push_back(0);
	FOR(i,N) {
		cin>>x;
		if(X.back()==x) continue;
		if(X.size()>=2 && X[X.size()-2]<X.back() == X.back()<x) X.pop_back();
		X.push_back(x);
	}
	
	ll dif=0;
	if(X.size()>=2&&X[1]<0) {
		dif=-X[1];
		X.erase(X.begin());
		FORR(x,X) x+=dif;
	}
	
	FOR(i,X.size()) {
		S.insert(i);
		if(i) {
			D[i-1]=abs(X[i]-X[i-1]);
			dif+=D[i-1];
			cand.insert({D[i-1],i-1});
		}
	}
	
	FOR(i,Q) cin>>x, VV.push_back({x,i});
	sort(ALL(VV));
	int pre=0;
	FORR(v,VV) {
		
		while(cand.size() && cand.begin()->first<=v.first) {
			x=cand.begin()->second;
			cand.erase(cand.begin());
			dif-=D[x]-pre;
			y=*S.lower_bound(x+1);
			if(y<*S.rbegin()) {
				cand.erase({D[y],y});
				dif-=D[y]-pre;
			}
			S.erase(y);
			auto it=S.lower_bound(x+1);
			if(it==S.end()) continue;
			y=*it;
			assert(x%2==y%2);
			
			
			if((x%2==0 && X[y]>=X[x]) || (x%2==1 && X[y]<=X[x])) {
				if(y<*S.rbegin()) {
					cand.erase({D[y],y});
					dif-=D[y]-pre;
				}
				S.erase(y);
				
				it=S.lower_bound(x+1);
				if(it!=S.end()) {
					D[x]=abs(X[x]-X[*it]);
					cand.insert({D[x],x});
					dif+=D[x]-pre;
				}
			}
			else {
				S.erase(x);
				it=S.lower_bound(y);
				if(it==S.begin()) {
					dif+=abs(X[x]-X[y]);
				}
				else {
					x=*--it;
					cand.erase({D[x],x});
					dif-=D[x]-pre;
					D[x]=abs(X[x]-X[y]);
					cand.insert({D[x],x});
					dif+=D[x]-pre;
				}
			}
		}
		
		dif -= (v.first-pre)*cand.size();
		ret[v.second]=dif;
		pre=v.first;
		
	}
	
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

色々バグらせたが、最終的には解けて良かった。