yukicoder : No.2009 Drunkers' Contest

あんまりお酒飲んでコンテスト出たことないな。
https://yukicoder.me/problems/no/2009

問題

N個の問題を順に解く。
途中、任意のタイミングで任意の量のお酒を飲めるとする。
もしここまで飲んだお酒の量がxであるとき、i問目を解くのにかかる時間はA[i]/(1+x)+B[i]*(1+x)となる。

最適なタイミングで最適な量のお酒を飲む時、全問題を解き切る最小時間はいくつか。

解法

i問目と(i+1)問目の間にお酒を追加で飲むべきか考える。
A[i]/B[i]＞A[i+1]/B[i+1]の時、2問の間でお酒を飲む意義はない。
この場合、2つの問題をくっ付けて考えてよい。

こうすると、最終的にA[i]/B[i]が昇順となるようになる。
この場合、必要なお酒の最適量も昇順になるので、各問の前にお酒を飲むことで時間が短縮できる限り飲むようにすればよい。

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

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];
	
	vector<ll> X,Y;
	X={A[0]};
	Y={B[0]};
	for(i=1;i<N;i++) {
		ll a=A[i];
		ll b=B[i];
		while(X.size()&&(__int128)X.back()*b>(__int128)Y.back()*a) {
			a+=X.back();
			b+=Y.back();
			X.pop_back();
			Y.pop_back();
		}
		X.push_back(a);
		Y.push_back(b);
	}
	double cur=1;
	double sum=0;
	FOR(i,X.size()) {
		if(X[i]>Y[i]) {
			double best=sqrt((double)X[i]/Y[i]);
			cur=max(best,cur);
		}
		sum+=X[i]/cur+Y[i]*cur;
	}
	_P("%.12lf\n",sum);
	
}

まとめ

シンプルでいいな。