ARC139 B - Make N (500)
コンテスト中の考察
$ A増加、$ B増加の回数とコストは二次関数になると思い三分探索
解説の解法
$ A増加,$ B増加のそれぞれの操作について1増加の方が安いならコストをそれで上書き
$ Aの方が効率の良い増加方法になるように必要ならswapする
$ A増加させる操作の最大回数は$ \lfloor \frac{n}{x} \rfloor
$ B増加させる操作の最大回数は$ \min(\lfloor \frac{n}{b} \rfloor, A - 1)
$ A回以上やるなら$ B増加させるのを$ A回減らして、代わりに$ A増加させるのを$ B回増やせば良くなる
操作回数の少ない方の操作回数を全て試す
これは最大でも$ \sqrt{N}になる
以上をテストケース毎に試すので$ \mathcal{O}(T \sqrt{N})