AtCoder Beginner Contest 040 B - □□□□□

ABCのBなのに、難しいと感じた人が多かった問題。 1回REでWAを出してしまった。

問題概要

(リンク)http://abc040.contest.atcoder.jp/tasks/abc040_b
n枚のタイルを敷き詰めて、長方形を作る。
その時、短辺と長辺の差 + 余ったタイルが最小になるようにする。

解法

愚直に実装する。
短辺と長辺の組み合わせをすべて試す。
O(sqrt(n))
ans = min (ans, abs(短辺-長辺) + n % (短辺×長辺))

なぜ難しい

短辺と長辺の差に着目すると、1辺をnのルートに近づければいいのでO(1)で求められそうな気がする。
その方向で考えをすすめるとハマる。
あと、短辺と長辺を全て考える時、調べる範囲を適当にすると短辺×長辺が0になる時、余りが計算できずREになった。