yukicoder : No.3604 Min of Max of Div of Sum

なるほど。
https://yukicoder.me/problems/no/3604

問題

N要素の整数列A,Bが与えられる。

を求めよ。

解法

１つ目のminについては、解vを二分探索し、その下限を求めよう。
vを仮決めしたとき、そのvが真の解以上であるためには、C[i]=A[i]-v*B[i]としたとき、各C[k]を含む連続部分列の和が0以上にできればよいことになる。
これはC[k]のprefix sum maximumとsuffix sum maximumを求めて行けば、全部でO(N)で確認できる。

int N;
ll A[101010],B[101010];
double L[101010],R[101010];

int ok(double v) {
	int i;
	R[N+1]=0;
	FOR(i,N) L[i+1]=max(0.0,L[i]+A[i]-v*B[i]);
	for(i=N-1;i>=0;i--) R[i+1]=max(0.0,R[i+2]+A[i]-v*B[i]);
	FOR(i,N) {
		double a=A[i]-v*B[i]+L[i]+R[i+2];
		if(a<0) return 0;
	}
	return 1;
}

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];
	double L=0,R=1e10;
	FOR(i,200) {
		double M=(L+R)/2;
		if(ok(M)) L=M;
		else R=M;
	}
	_P("%.12lf\n",L);
}

まとめ

C[i]を作って以降の部分が詰め切れなかった。