AtCoder Beginner Contest 174, E : Logs

問題文

　https://atcoder.jp/contests/abc174/tasks/abc174_e

問題概要

　丸太が $N$ 本あり，$i$ 番目の丸太の長さは $A_i$ です．
　この丸太を，合計 $K$ 回まできることができるとき，最も長さい丸太の長さとして有り得る値の最小値はいくらか？　小数点以下を切り上げて出力せよ．

制約

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq K \leq 10^9$
• $1 \leq A_i \leq 10^9$

解法

　まず，真の答えが小数になるかのような問題文になっていますが，整数だけ考えれば大丈夫です．というのも，小数部分があるような長さで切るよりは，切り上げた長さで切ってしまった方が，残りの丸太が短くなるので目標を達成しやすくなるからです．
　解法ですが，次の 2 つのことが言えることから，二分法で答えを求めることができます．

• ある長さを達成できるとき，それより長い長さは（元々の丸太の長さの最大値までの範囲で）達成できる
• 解となる長さを固定したとき，各丸太を切らなければならない回数を（ある程度高速に）計算できる

それぞれ見ていきましょう．
　前者については，ほぼ自明と言ってしまってよいかなと思います．長さの最大値をとっている丸太の切り口をずらしていくなどすると割と自由な長さを切り出せます．
　後者については，各丸太ごとに切らなければならない回数を求め，その和をとることになります．長さが $a$ の丸太を，出来上がりが全て長さ $L$ 以下になるように切るときに切らなければならない回数を考えます．$L$ は固定なので $a$ の変化に応じてどう答えが変わるかと考えると，$a \leq L$ のとき $0$ ，$L < a \leq 2L$ のとき $1$ ……，となっていて，$\frac a L$ の切り上げから $1$ 引いた値になっています．よって，プログラム上では ( a + L - 1 ) / L - 1 というのが，長さ $a$ の丸太を切る回数です．これを全丸太について足して $K$ 以下になっているかどうかを判定することで，固定した解を達成できるかどうかを判定することができます．
　この二分法をやったとき，判定部分には $\Theta( N )$ 時間がかかり，解が存在する範囲の初期値は $( 0, \max A ]$ なので，$O( \max A \log N )$ 時間で問題を解くことができます．

コード

int check( const VI &A, const int L )
{
	int res = 0;

	FOR( a, A )
	{
		res += ( a + L - 1 ) / L - 1;
	}

	return res;
}

int main()
{
	IN( int, N, K );
	VI A( N );
	cin >> A;

	int lb = 0, ub = 1'000'000'000;
	while ( lb + 1 < ub )
	{
		const int mid = ( lb + ub ) / 2;
		( check( A, mid ) <= K ? ub : lb ) = mid;
	}

	cout << ub << endl;

	return 0;
}