Résumé Review - #639 div2 f - tac

bi が x (= bi + 1) になったとする
$\Delta_i (x) = x(a_i - x^2) - (x - 1)(a_i - (x - 1)^2)$
$= a_i - 3x^2 + 3x - 1$

上に凸な曲線で, x = 1/2 で最大値をとる
x ≥ 1 で減少する

貪欲に n つから一番大きな $\Delta_i (x)$ が得られる i を探すのを k 回する

$\Delta_i (x)$ は減少するだけだから貪欲に大きいのをとっていい
一番大きいのを取らなかったら, 一番大きいのを取るのに変えて悪くなることはない

一番大きい ( $\Delta_i (x)$ が) のが i とする
二番目に大きい j の以下になるまでは bi を +1 し続ける

二分探索で, n つに共通の $\Delta_i (x)$ の下限 A を決める
ある i, j で A が異なれば, 下限が大きい方を下限が小さい方になるまでとった方がいい