Codeforces #286 Div1 C. Mr. Kitayuta vs. Bamboos

似た問題をyukicoder向けに考えてたけど自分で解法を求める前にCFで出てしまった。
おかげに自分で解けてない。
http://codeforces.com/contest/506/problem/C

問題

N本の竹がある。
各竹は最初H[i]の高さで、以後１日毎にA[i]だけ高さが伸びる。
１日のはじめ、ハンマーを使って１か所の竹を選択してmin(P,竹の高さ)分竹の高さを短くする、という処理を最大K回行える。

最適にハンマーを使った場合、M日後の最高の竹の最小値を求めよ。

解法

M日後の最高の丈の高さVを二分探索する。
後はM日後に各竹を高さV以下に出来るかを考えればよい。

まず、各竹をハンマーでたたく回数T[i]はであり、各竹の回数の総和がK*M回を超えるなら条件を満たせない。
各竹を叩く日はできるだけ早い方がよく、T[i]回それぞれ最も遅くてどの日に叩かなければならないかを求め、各日にたたく回数をK回以内に抑えられるかを判定すればよい。

あとは「最も遅くてどの日に叩かなければならないか」を求めればよい。
叩かなければならない高さD=H[i]+M*A[i]-Vとする。
叩く回数はceil(D/P)回で合計Dだけ叩くには、初回は長さがD%Pを超えたタイミング、２回目以降は長さがDを超えたタイミングでたたけばよい。

int N,M,K,P;
ll H[101000],A[101000];

bool ok(ll V) {
	ll tot=0;
	int i;
	FOR(i,N) tot += max(0LL, (H[i]+M*A[i]-V+(P-1))/P);
	if(tot>M*K) return false;
	int day[5005]={};
	FOR(i,N) {
		if(H[i]+M*A[i]<=V) continue;
		ll dif=H[i]+M*A[i]-V;
		for(ll d=(dif%P==0)?P:dif%P; d<=dif; d+=P) {
			ll da=max((d-H[i]+A[i]-1)/A[i],0LL);
			if(da>=M) return false;
			day[da]++;
		}
	}
	ll left=0;
	FOR(i,M) {
		left += day[i];
		left = max(0LL,left-K);
	}
	return left==0;
	
}

まとめ

早く作問しないと問題がネタ被りするなぁ。