Codeforces ECR #066 : G. Yet Another Partiton Problem

こういう一見シンプルなのに解法がややこしい問題苦手。
https://codeforces.com/contest/1175/problem/G

問題

N要素の整数列Aが与えられる。
これらを連続するK個の部分列に分けたい。
その際、部分列のコストは、(部分列の要素数)×(最大値)とする。
最適な分割をしたとき、総コストを最小化せよ。

解法

以下、EditorialにあるConvex Hull Trick + Li Chao Tree解法ではなく、こちらのコメントにあるConvex Hull + 分割統治法を紹介。

f(i,j) := Aのprefix i個をj個の部分列に分割するときの総コストの最小値
とする。jを1からKまで順に埋めていこう。
すなわち、f(*,j-1)がすべて求められているとき、f(i,j)を埋めていく。

さて、L≦i＜i'＜Rの範囲で、f(i'.j-1)→f(i,j)の遷移を求めることを考えよう。
分割統治法なので、M=(L+R)/2としたとき、まずL≦i＜i'＜MのケースとM≦i＜i'＜Rのケースは再帰的に求めてしまおう。
残りはL≦i＜M≦i'＜Rのケースである。

P[i]=max(A[i...M])、Q[i']=max(B[M..i'])とする。
するとf(i',j) = min(f(i,j-1)+(i'-i)*max(P[i],Q[i']))となる。
さて、ここで式の後半がi'の一次式なのでConvex Hull Trickを使いたいのだが、maxの中身をP[i]とQ[i']どちらを使うべきか悩ましい。

ここでP[i]はiが小さくなるほど大きくなり、Q[i']はi'が大きくなるほど大きくなる。
よって、i'をずらしていくと、maxのうちQ[i]'を取るべきケースが徐々に増えていく。
これを用いて必要なP[i]に関する式だけ入れた一次式の集合と、Q[i']に関する式だけ入れた一次式集合の最小値を取るようにする。

int N,K;
int A[20202];
ll from[20202];
ll to[20202];
int X[20202],Y[20202];

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	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 ((A.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-A.first));
	}
	void add(V a, V b) { // add ax+b
		if(Q.size() && Q.back().first==a) {
			//aが同じ場合
			if(b>=Q.back().second) return; //minの場合
			Q.pop_back();
		}
		Q.push_back({a,b});
		int v;
		while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
			Q[v-2]=Q[v-1], Q.pop_back();
	}
	V query(V x) {
		if(Q.empty()) return 1LL<<30;
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			(((calc(Q[M],x)>=calc(Q[M+1],x)))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};

void hoge(int L,int R) {
	if(L+1==R) return;
	int M=(L+R)/2;
	hoge(L,M);
	hoge(M,R);
	
	int i;
	X[M-1]=0;
	Y[M]=0;
	for(i=M-1;i>=L;i--) Y[i]=max(Y[i+1],A[i]);
	for(i=M;i<R;i++) X[i]=max(X[i-1],A[i]);
	
	ConvexHull<ll> chtX,chtY;
	int cur=M-1;
	for(i=M;i<R;i++) {
		while(cur>=L && Y[cur+1]<=X[i]) {
			chtX.add(cur,from[cur]);
			cur--;
		}
		to[i]=min(to[i],chtX.query(-X[i])+i*X[i]);
	}
	cur=L;
	for(i=R-1;i>=M;i--) {
		while(cur<M && Y[cur+1]>=X[i]) {
			chtY.add(Y[cur+1],from[cur]-Y[cur+1]*cur);
			cur++;
		}
		to[i]=min(to[i],chtY.query(i));
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i+1];
		from[i+1]=1LL<<30;
	}
	
	while(K--) {
		FOR(i,N+1) to[i]=1LL<<30;
		hoge(0,N+1);
		swap(from,to);
	}
	
	cout<<from[N]<<endl;
}

まとめ

これ本番で解ける気がしないなぁ。