公式解説 https://atcoder.jp/contests/abc204/editorial/224 で記されている \(f(t):=t+C_i+\left\lfloor \frac{D_i}{t+1}\right\rfloor\) の最小値を求めるパートについて解説します。その他については、公式解説と同様です。

\(f(t)\)は広義単調減少/増加なので三分探索などでは求められません。

三分探索するには狭義単調減少/増加である必要があるためです。

床関数を取り除いた \(h(t):=t+C_i+\frac{D_i}{t+1}\) を考えます。

\(t\) が整数の範囲では \(t+C_i = \left\lfloor t+C_i\right\rfloor\)なので、\(f(t)=\left\lfloor t+C_i+\frac{D_i}{t+1}\right\rfloor=\left\lfloor h(t)\right\rfloor\) となります。

\(a<b\) のとき\(\left\lfloor a\right\rfloor≦\left\lfloor b\right\rfloor\)となるので、\(h(x)\)が最小となる\(x\)では\(f(x)\)も最小となります。

一旦、\(t\) が実数の範囲で考えます。\(h(t)\)が最小になるとき\(t=x\)とします。

\(t≦x\)の範囲では\(h(t)\)は狭義単調減少、\(x≦t\)の範囲では\(h(t)\)は狭義単調増加になるので三分探索などで\(x\) の値を求められます。

求めたいのは \(t\) が整数の範囲なので、 \(f(\left\lfloor x\right\rfloor)\)か\(f(\left\lceil x\right\rceil)\)で最小値になります。