Codeforces ECR #061 : D. Stressful Training

D意外に解かれてないな。
https://codeforces.com/contest/1132/problem/D

問題

N個のPCがある。
初期状態でバッテリーはA[i]たまっており、1分毎に残量がB[i]減る。

なお、毎分１つのバッテリーを選択し、残量の減少ペースをC減少させることができる。
ここでK分経過する間、どのバッテリーも残量が負にならないようにしたい。
そのためのCの最小値を求めよ。

解法

二分探索で求める。
よってCが決まったとき、条件を満たすバッテリーの選択順を求めよう。

まずバッテリーの必要チャージ回数の総和を求める。
これがK以上だとどうしようもない。
次に、各バッテリーについて最低このタイミングまでに1回選択しないといけない、というタイミングを列挙しよう。
その後のタイミングの累積和を取り、n分目までに(n+1)回以上の選択を要するようなことがあれば条件を満たせない。

int N,K;
ll A[202020],B[202020];
int cand[202020];

int hoge(ll v) {
	ll num=0;
	int i;
	FOR(i,N) {
		ll x=A[i]-K*B[i];
		if(x<0) {
			if(v==0) return 0;
			x=-x;
			num+=(x+(v-1))/v;
		}
	}
	if(num>K) return 0;
	ZERO(cand);
	FOR(i,N) {
		ll cur=A[i];
		while(cur-B[i]*K<0) {
			ll ng=cur/B[i]+1;
			cand[ng]++;
			cur+=v;
		}
	}
	
	ll sum=0;
	for(i=1;i<=K;i++) {
		sum+=cand[i];
		if(sum>i) return 0;
	}
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	K--;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	ll ret=(1LL<<43)-1;
	if(hoge(ret)==0) return _P("-1\n");
	for(i=42;i>=0;i--) if(hoge(ret-(1LL<<i))) ret-=1LL<<i;
	cout<<ret<<endl;
	
	
}

まとめ

Kがさほど大きくないのがカギだね。