AtCoder ABC #174 : E - Logs

最近のABCでは簡単な方？
https://atcoder.jp/contests/abc174/tasks/abc174_e

問題

初期状態でN個の丸太があり、それぞれの長さが与えられる。
これらに最大K回切断を行ったとき、最長の丸太の長さの最小値を小数点以下切り上げした値を求めよ。

解法

f(L) := 全部の丸太を長さL以下にするときの最小切断回数

とすると、この関数の値は単調減少になるので、Lを二分探索するとよい。
長さMの丸太をL以下にする切断数はfloor((M-1)/L)で計算できる。

int N;
ll K;
ll A[202020];

ll cut(ll v) {
	ll num=0;
	int i;
	FOR(i,N) {
		num+=(A[i]-1)/v;
		if(num>K) return num;
	}
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	
	ll L=(1<<30);
	
	for(i=29;i>=0;i--) {
		if(cut(L-(1<<i))<=K) L-=1<<i;
	}
	cout<<L<<endl;
}

まとめ

なんか似たようなの見たことあったと思ったけど、蟻本の二分探索の項目だね。
まだ前半の方だし、蟻本をサラッとでも見たのならすぐに思い出したいところ。