ABC296-D M<=ab の解き方 - ごりちゃんがゆく

先日コンテスト中に緑diffの問題が解けなくて悔しかったので、久々にブログ書いてみます！
どういう思考をたどれば解けた可能性があるのか振り返っていきます。

問題概要

問題のリンク
* 正整数 $N, M$ が与えられる。
* $1$ 以上 $N$ 以下の整数 $a,b$ を選んだとき、 $X=ab$ の積が $M$ 以上になるようなものの中で最小の値を求める。
* そのような値が存在しなければ $-1$ を出力する。

制約

$1 \leq N,M \leq 10^{12}$

結構でかいので工夫が要りそうですね。
計算量を $\sqrt{N}$ や $\sqrt{M}$ ぐらいに抑えたい感じの印象です。

考察

視覚的なイメージ

$ab$ の積を扱うので、横 $a$ , 縦 $b$ の長方形を考えると視覚的にとらえやすい気がしました

で、これがどうなってると良いかというと、面積が $M$ 以上になれば良いので、下図の青いらへんのゾーンに $(a,b)$ を選べば良いです！

$M = ab$ がボーダーなんですけど、 $M = ab$ を変形すると $b = \frac{M}{a}$ になって、反比例の式 $y = \frac{a}{x}$ と形が一緒ですね。

aを固定する

で、図を描いてみたは良いが、これだけだとまだどこから手を付けて良いか分からなさがありますね
$N*N$ 通り探索するのは範囲が多すぎる！
こういうとき片方を固定すると良いことがあるので $a$ を固定して考えてみます
$a$ の値が決まってれば、 $ab \geq M$ を満たす最小の $b$ だけ考えればよくなって、これって計算で求められそう！
実際に、そのような $b$ は $\lceil \frac{M}{a} \rceil$ (天井関数) で求められます！

計算量をどうする？

$a$ を固定すれば最適な $b$ が求まることがわかったところで、まだもう1ステップ考えることがあって、計算量の壁です！
このままだとまだ $a$ を $N$ 通り探索いなきゃいけない気持ちになりますよね。
どうしましょう！
(ここ普通に難しいと思った)
実は $a$ と $b$ は対等な関係なので、 $a \leq b$ と仮定してよいです！ ( $a \leq b$ としても一般性を失わない みたいな表現をされるやつ) です！
$a \gt b$ となったら探索を打ち切って良いのです！
$a*b$ が大体 $M$ なので、この仮定をいれることによって計算量が大体 $\sqrt{M}$ になるはずです。

ACコード

こちらはコンテスト後に通ったコードです。

N,M = map(int,input().split())

INF = float('inf')
ans = INF
for a in range(1,N+1):
    b = -(-M//a)
    if b > N: continue
    if b < a: break
    ans = min(ans, a*b)

print(-1 if ans==INF else ans)