Codeforces #189 Div1. C. Kalila and Dimna in the Logging Industry

これ、問題の意図を解釈するのにすごい手間取った…。
http://codeforces.com/contest/319/problem/C

問題

1～NのN本の木があり、高さA[i]はA[1]=1で以降単調増加である。

初期状態ではチェーンソーは任意の木を高さ1だけ減らすことができる。
高さ1を減らすと、チェーンソーは再充電が必要である。
この時のコストは、完全に切り倒した木で決まり、i番目の木を切り倒すとB[i]のコストで充電できるようになる。
B[i]は単調減少で、B[N]=0である。

すべての木の高さを0にするコストを求めよ。

解法

これ、初期状態では1番の木しか倒せないのね…そこに気づくまで時間かかった。
最後の木を倒すとB[N]=0なので後の木は倒し放題である。
よって、最後の木を切り倒すコストを求めればよい。

これはO(N^2)で解くことができ、x番目の木の切り倒すまでの総コストはi番目の木の次にx番目を切る場合と考えると、となる。
ただ、N<=10^5なのでO(N^2)では無理。

ただ、ここでB[i]が単調減少なことを用いると、先日使ったconvex hull trickを使えばO(N)で解ける。

int N;
ll A[100001],B[100001],T[100001];

// F[i] = T[j]*x + B[j];
ll f(int j,int x) { return T[j]+x*B[j];}
bool check(int f1,int f2,int f3) {
	// ll overflow
	double a1=B[f1], b1=T[f1];
	double a2=B[f2], b2=T[f2];
	double a3=B[f3], b3=T[f3];
	return (a2-a1)*(b3-b2) >= (b2-b1)*(a3-a2);
}

void solve() {
	int r,i,j,k,l,x,y,tx,ty;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	deque<int> D;
	D.push_back(0);
	for(i=1;i<N;i++) {
		while(D.size()>=2 && f(D[0],A[i]) > f(D[1],A[i])) D.pop_front();
		T[i] = f(D[0], A[i]);
		while(D.size()>=2 && check(D[D.size()-2],D[D.size()-1],i)) D.pop_back();
		D.push_back(i);
	}
	cout << T[N-1] << endl;
	return;
}

まとめ

convex hull trick、まだすらすらと書けないのでもう少し練習が必要かな。