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になった。