Codeforces #351 Div1 C. Levels and Regions

CHTだろうとまでは推測ついても、そこから式を立てるのが下手。
http://codeforces.com/contest/674/problem/C

問題

N個のレベルからなるゲームがある。
各レベルはパラメータT[i]を持つ。
このゲームをK個の連続したRegion(レベル群)に分割する。

各Regionは以下のように攻略する。
Region内のレベルは先頭から順にクリアする。
既にクリアしたレベルをx..(y-1)、未クリアの最初のレベルをyとすると、1の時間を掛けてレベルyをクリアできる確率はT[y]/sum(T[x]..T[y])である。

最適にRegion分割をした場合、全Regionをクリアする時間の期待値の最小値を求めよ。

解法

Convex Hull Trickで解く。
dp[x][i] := レベル1～xをi個のregionに分割したとき、i個のregionをすべてクリアするまでの時間の期待値の最小値
f(L,R) := レベル(L+1)～Rからなる単一Regionをクリアする時間の期待値
とする。
dp[R][i] = min_L(dp[L][i-1] + f(L,R))となるのは容易に想像がつくが、f(L,R)がO(1)で計算できてもこのDPはO(N^2*K)かかってしまう。
そこで、CHTでLの最小値を高速に求めよう。

前計算で以下の値を計算しておき、f(L,R)を変形する。

• 
• 
• 

より、-S(L)*RevSum(R) + S(L)*RevSum(L)-f(0,L)をRevSum(R)の一次関数と置けるうえ、Rが大きくなるとRevSum(R)も大きくなるのでCHTで最小値が容易に取れるようになる。

int N,K;
int T[202020];
ll TS[202020];
double S[202020];
double Rev[202020];
double RS[202020];
double from[202020];
double to[202020];

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	int cmptype=0; // 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_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();
	}
	void add(vector<pair<V,V>> v) {
		sort(v.begin(),v.end());
		if(cmptype==1) reverse(v.begin(),v.end());
		for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second);
	}
	
	
	V query(V x) {
		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 solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	for(i=1;i<=N;i++) {
		cin>>T[i];
		TS[i]=TS[i-1]+T[i];
		Rev[i]=Rev[i-1]+1.0/T[i];
		from[i]=S[i]=S[i-1]+TS[i]*1.0/T[i];
	}
	
	for(i=2;i<=K;i++) {
		ConvexHull<double> ch;
		for(j=1;j<=N;j++) {
			if(j<=i) to[j]=j;
			else to[j]=-ch.query(Rev[j])+S[j];
			ch.add(TS[j],-(from[j]+Rev[j]*TS[j]-S[j]));
		}
		swap(from,to);
	}
	
	_P("%.12lf\n",(double)from[N]);
}

まとめ

毎回CHTは式変形が出来ず失敗する。