https://prd-xxx.hateblo.jp/entry/2023/04/04/211848

先日コンテスト中に緑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)

6行目の -(-M//a) はpythonで使える切り上げテクです！ (M を a で割ったあまりを整数に切り上げています)
とっさに使えると強いです！
8行目の break はTLEしないために大事です。

なぜ解けなかった？

まともな考察が踏めてませんでした　あたまがごりちゃん
$X$ の値を決めて約数を列挙するみたいな発想しか浮かばなくて沼ってました
間違った方針に行くとかなり沼るやつでしたね。。
こういうのを安定して解けるようになりたい。

おわり

冷えたけど、学びの多い良問でした！
青コーダーだけど ABC-D にも学びがある！