Codeforces #424 Div1 C. Bamboo Partition

しょうもないミスで落とした…。
http://codeforces.com/contest/830/problem/C

問題

N個の竹がある。
各竹は初期状態で高さ0であり、以後1日毎に1高さが伸びる。

ここで、i番目の竹の高さがA[i]を超えた時点で刈ることを考える。
ただ、いつも刈ることができるわけではない。
整数dを定めたとき、dの倍数の日にのみ刈ることができる。
また、刈った際にA[i]を超えた分は余りとなる。

さて、あまりの竹の総長がK以下で済むようなdの最大値を求めよ。

解法

dが定まれば余る竹の総長もO(N)で容易に求まる。
ただこの総長はdに対し単調増加ではないため二分探索などは使えない。
そこで、平方分割の要領でdの検索範囲を絞ろう。

各竹についてdの何倍の時点で刈るかを考える。
すなわち、d*B[i]が初めてA[i]を超えるようなB[i]を考える。
B[i]が変化しない範囲では、dが小さいほど余りの丈の総長も短くなる。

dが小さい範囲(√max(A)以下)はdを総当たりし、dが大きい範囲では、B[i]が変化しない範囲で余る竹の総長がKを超えない最大のdを求めよう。

ll N,K;
ll A[2020];
vector<ll> cand;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		for(x=1;x<=min(A[i],100000LL);x++) {
			if(A[i]/x>=100000) cand.push_back((A[i]-1)/x);
		}
	}
	
	for(x=1;x<=100000;x++) cand.push_back(x);
	
	cand.push_back(1LL<<40);
	cand.push_back(1LL<<41);
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	
	ll ma=1;
	FOR(i,cand.size()-1) {
		ll pre=cand[i-1];
		ll now=cand[i];
		
		ll num=0,sum=0;
		FOR(x,N) {
			num+=(A[x]+now-1)/now;
			sum+=(A[x]+now-1)/now*now-A[x];
		}
		
		if(sum<=K) ma=now;
		else {
			ll del=sum-K;
			ll hoge=now-(del+(num-1))/num;
			if(hoge>pre) ma=hoge;
		}
	}
	
	cout<<ma<<endl;
}

まとめ

±1のミスで落とした。これだから平方分割は怖い…。