問題

$g=1$ である. 次の行動を $0$ 回以上行うことができる.

その直後に $\dfrac{A}{\sqrt{g}}$ 秒かけてミッションを敢行する.

ミッション敢行するために必要な最小時間を求めよ.

$k \geq 0$ で定義された関数 $f$ を $f(k):=Bk+\dfrac{A}{\sqrt{k+1}}$ とする. このとき, $K$ 回 $g$ に $1$ を加算した場合の所要時間が $f(K)$ になる.

$f'(k)=B-\dfrac{A}{2(k+1)^{3/2}}, \quad f''(k)=\dfrac{3A}{4 (k+1)^{5/2}}$

よって, $f$ は下に凸な関数である.

また, $K \geq \dfrac{A}{B}$ のとき, $f(K) \geq BK \geq A=f(0)$ であるから, $0 \leq K \leq \dfrac{A}{B}$ の範囲に絞っても良い.

従って, $f$ を $0 \leq K \leq \dfrac{A}{B}$ の範囲で三分探索を行えば良い.

計算量は $O(\log A)$ 時間である.

Kazun の競プロ記録