Codeforces #262 Div2 C. Present

CF262に参加。
C,Dが何とか解けて好順位につけたので良かったが、Eが惨敗だったのは反省。
http://codeforces.com/contest/460/problem/C

問題

N要素の数列A[i]がある。
Aのうち連続するW個をインクリメントする、という処理をM回行う。
Aの最小値を最大化せよ。

解法

Aの最小値を二分探索し、M回のインクリメントで全要素が仮置きの最小値Pを越えられるか判定すればよい。
判定は処理では、A[i]

int N,M,W;
ll A[200000],S[200000];

int ok(ll H) {
	int i;
	ll L=M,SS=0;
	ZERO(S);
	FOR(i,N) {
		SS-=S[i];
		if(A[i]+SS<H) {
			ll D=H-A[i]-SS;
			if(D>L) return 0;
			SS+=D;
			L-=D;
			S[i+W]+=D;
		}
	}
	return 1;
}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M>>W;
	FOR(i,N) cin>>A[i];
	
	ll ret=0;
	for(i=40;i>=0;i--) if(ok(ret+(1LL<<i))) ret |= (1LL<<i);
	cout<<ret<<endl;
}

まとめ

これは割とすんなり。