AtCoder ABC 040 B – □□□□□ Python解説
□□□□□
高橋君は大きさ 1メートル四方のタイルを n枚持っています。
高橋君はこれらのタイルのうちいくつかを、重ならないように隙間なく並べて大きな長方形を作ろうとしています。
出来上がる長方形はできるだけ正方形に近いほうがよいですが、同時に、使わずに余るタイルの枚数ができるだけ少なくなるようにしたいと考えています。長方形の縦と横の長さの差の絶対値と、余ったタイルの枚数の和を最小でいくつにできるでしょうか。
AtCoder株式会社 AtCoder Beginner Contest 040
考えられる組み合わせをひとつひとつ調べて、それぞれのタイルの余り、縦と横の差を比べていきましょう。
とりあえず愚直にfor文の2重ループ。
n = int(input())
ans = 100000
for y in range(1, n + 1):
for x in range(1, n + 1):
if x * y > n:
break
else:
mod = n - (x * y)
diff = abs(x - y)
ans = min(ans, (mod + diff))
print(ans)愚直な2重ループなので実行時間がかなり危ういですが、上記のコードでも一応正解になります。とりあえず、最小値を調べるということで、ansに100000を入れて最小値を更新するたびに変更するようにしています。
後はループでタイルの数を超えた場合にはbreak文でループを終了しています。
次はループの数を減らしたバージョン。
n = int(input())
ans = 100000
for i in range(1, n + 1):
mod = n - (i * (n // i))
diff = abs(i - (n // i))
ans = min(ans, (mod + diff))
print(ans)
縦と横を工夫することでループに掛かる時間を節約できます。こちらなら制限時間的にも余裕があります。
さらにもう一つ。
import math
n = int(input())
ans = 100000
for i in range(1, int(math.sqrt(n)) + 1):
mod = n - (i * (n // i))
diff = abs(i - (n // i))
ans = min(ans, (mod + diff))
print(ans)調べるタイルの数はnの2乗根まででも大丈夫なので、sqrtで2乗根までのループにしています。