竸プロ精進記 ABC040 B □□□□□ python 3

問題:https://atcoder.jp/contests/abc040/tasks/abc040_b

可能な組み合わせを全探索し、それぞれの時のタイルの余り数、及び長方形の長辺と短辺の差が最小となる条件を探します。

コード例

N=int(input())
ans=1000000000000000000
mod=0
if N==1:
    print(0)
    exit()
for i in range(1,N):
    mod=N%i
    tmp=mod+abs(i-(N//i))
    #print(i,mod,tmp)
    if tmp<=ans:
        ans=tmp
print(ans)

7行目のfor文からが全探索している箇所です。タイルを縦にi個からN個並べて長方形を作ったとして、それぞれの場合で余るタイルの個数、長辺-短辺の長さを調べていきます。

余るタイルの個数はNをiで割った余りが相当します。紙に絵を書いてみればわかるでしょう。一片にi個並んでいるとして、長方形のもう一つの辺はNをiで割った商になります。この２つを足して、全ての場合において最も小さい値となった時の値を回答すればOKです。

iが1の場合の時がコーナーケースになっているので、iが1の時のみ回答0を出力するようにしておきます。(このコーナーケースに気づかずに一度WAを出しました^^)

今、この記事を書いていて気付きましたが、探索するのはNまでではなくて、√N個でも良いと思われます。縦長の長方形も横長の長方形も本問題においては等価になるので。入力される値の最大値がさらに大きい値の場合、たとえば10^9以上なら√N個までの探索で無いと間に合わないでしょう。