D - Freefall

下に凸な関数っぽい感じだったので、下のサイトを参考に三分探索しました。
三分探索を救いたい - Qiita

誤差が出てくるので、出てきた操作回数±10くらいの範囲を探索しました。
一応、ACできましたが、疑問がいくつか残ったままだったので、コンテスト後に調べてみました。

整数の三分探索の方法

公式解説によれば、繰り返しの条件をr - l > 2として、終了後にrからlまでの最小値を答えれば良いようです。
おそらく、3分する点がlと重複しない間は探索を繰り返すものと思います。

探索範囲の最大値

$t\geq \frac{A}{B}$ なら $f(t) \geq f(0)$ となるので解は $\frac{A}{B}$ 以下となる、ということらしいです。詳細は公式解説参照。

下に凸であることの判定

上に凸，下に凸な関数と二階微分 | 高校数学の美しい物語
上記サイトによれば、二階微分が非負整数なら下に凸と判定できるそうです。

ざっくりとした理由をメモしておきます。

まず、一階微分は接線の傾きであり、下に凸の場合単調非減少となる必要があるそうです。確かに、下に凸の二次関数などを例に考えれば、最小値より前は傾きが負で、最小値に近づくにつれてだんだん傾きは小さくなり(0に近づき)、最小値で0になります。そして、その後は傾きは正になり、傾きは大きくなっていくことが想像できます。
そして、傾きが単調非減少になるためには、傾きの変化量は常に非負である必要があるので、二階微分が非負になるということが理解できます。

高校数学から大分遠ざかっていたので、微分を思い出しながら実際にやってみます。

$f(x) = Bx+\frac{A}{\sqrt{x+1}}$