kmjp's blog

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

AtCoder ABC #275 : Ex - Monster

ARC

こういう問題、こうやれば計算量落とせるというのがわかっても、さっと書けないな。
https://atcoder.jp/contests/abc275/tasks/abc275_h

問題

N要素の整数列A,Bが与えられる。
任意の区間[L,R]に対応するA[L...R]内の全要素を1デクリメントするには、max(B[L...R])だけコストがかかるとする。
Aの全要素を0以下にするのにかかる総コストの最小値を求めよ。

解法

A[L...R]内だけ操作して、A[L...R]を0以下にするケースを考えてみる。
B[L...R]中の最大値をB[M]とする。
もしA[M]を含む区間をデクリメントする場合、区間を[L,R]全体にした方がお得である。

よって、[L,R]全体を何度かデクリメントした後は、[L,M-1]と[M+1,R]を別々に考えてよい。
この関係を二分木で表現する。

f(L,R,x) := 区間[L,R]に対し、すでにx回デクリメントが成されていた場合、A[L...R]を0以下にする最小コスト
とすると、A[M]を含む区間をあとy回デクリメントするとして
f(L,R,x) = min(y*B[M] + f(L,M-1,x+y) + f(M+1,R,x+y))
となる。

あとはf(L,M-1,*)とf(M+1,R,*)からf(L,R,*)を求めることを考える。
f(*,*,x)は、xに対し折れ線状のグラフとなり、傾きは0以下でありながらその傾きは徐々に0に向け増加する。

よってf(*,*,x)を以下のように管理しよう。

  • x=0の時の値
  • x=0の時の傾き
  • 傾きが変化するx座標の傾きの増分を、mapで持つ

まずf(L,R,x) = f(L,M-1,x) + f(M+1,R,x)を計算しようとすると、上記上2つの値は和を取るだけで良く、3つ目はマージテクの要領でmapのマージをすればよい。

その後、傾きが-B[M]より小さい部分については-B[M]に補正し、合わせてx=0の時の値を小さく補正しよう。
最終的にf(0,N-1,0)が解。

int N;
ll A[101010],B[101010];

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=0;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return max(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(def,i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,NV);
		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]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_Pair<int,1<<20> st;

ll X[101010],Y[101010];
map<ll,ll> M[101010];

int dfs(int CL,int CR) {
	if(CL>CR) return -1;
	int cur=st.getval(CL,CR+1).second;
	int x=dfs(CL,cur-1);
	int y=dfs(cur+1,CR);
	
	if(x!=-1) Y[cur]+=Y[x], X[cur]+=X[x];
	if(y!=-1) Y[cur]+=Y[y], X[cur]+=X[y];
	if(x==-1&&y==-1) {
		;
	}
	else if(x==-1) {
		swap(M[cur],M[y]);
	}
	else if(y==-1) {
		swap(M[cur],M[x]);
	}
	else {
		if(M[x].size()<M[y].size()) swap(x,y);
		FORR2(a,b,M[y]) M[x][a]+=b;
		swap(M[cur],M[x]);
	}
	
	while(M[cur].size()) {
		auto it=M[cur].begin();
		if(it->first<=A[cur]||X[cur]-it->second>=B[cur]) {
			Y[cur]-=it->first*it->second;
			X[cur]-=it->second;
			M[cur].erase(it);
		}
		else {
			break;
		}
	}
	
	if(X[cur]>B[cur]) {
		auto it=M[cur].begin();
		Y[cur]-=it->first*(X[cur]-B[cur]);
		M[cur][it->first]-=(X[cur]-B[cur]);
		X[cur]=B[cur];
	}
	
	Y[cur]+=(B[cur]-X[cur])*A[cur];
	M[cur][A[cur]]+=B[cur]-X[cur];
	X[cur]=B[cur];
	/*
	cout<<cur<<" "<<x<<" "<<y<<" "<<X[cur]<<" "<<Y[cur]<<" ";
	FORR2(a,b,M[cur]) cout<<a<<":"<<b<<" ";
	cout<<endl;
	*/
	
	return cur;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
	}
	FOR(i,N) {
		cin>>B[i];
		st.update(i,B[i]);
	}
	
	int root=dfs(0,N-1);
	cout<<Y[root]<<endl;
}

まとめ

折れ線グラフの和を取る問題に対し、今回のテクは利用できそうだね。