Codeforces #320 Div1 C. Weakness and Poorness

Dynamic Scoringのおかげでうまみの無い問題。
http://codeforces.com/contest/578/problem/C

問題

N要素の整数列A[i]がある。
ある実数xに対し、B[i]=A[i]-xで生成される数列を考える。

数列のpoornessとは、各要素の和の絶対値である。
数列のweaknessとは、その数列の連続部分列全パターンにおけるpoornessの最大値である。

xを任意に選択できるとき、B[i]のwealknessの最小値を求めよ。

解法

S[i]=sum(B[0..i])とすると、Bのweaknessはmax(S)-min(S)であり、O(N)で求められる。
Bのweaknessはxに対して下に凸なので、xを３分探索すればよい。

int N;
ll A[202020];

double dodo(double v) {
	double sum=0;
	double mi=0,ma=0;
	double tma=0;
	int i;
	
	FOR(i,N) {
		sum += A[i]-v;
		tma=max(tma,abs(sum-ma));
		tma=max(tma,abs(sum-mi));
		
		ma=max(ma,sum);
		mi=min(mi,sum);
	}
	return tma;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	double L=*min_element(A,A+N);
	double R=*max_element(A,A+N);
	
	FOR(i,200) {
		double m1=(2*L+R)/3;
		double m2=(2*R+L)/3;
		
		if(dodo(m1)<dodo(m2)) R=m2;
		else L=m1;
	}
	_P("%.12lf\n",dodo(L));
}

まとめ

なんでpoorness/weaknessという名前を振ったんだろう。