ABC040-B - □□□□□ を解く

ABC040-B - □□□□□

今回は少し難しそうだ

N枚のタイルをできる限り余らせずに、正方形寄りの長方形を作る問題

厳密には

「長方形の縦と横の長さの差の絶対値と、余ったタイルの枚数の和の最小」

を求める必要がある

とりあえず手当たり次第に長方形を作って、上記の値を求めてみたい

とはいえ、作れる長方形全てのシミュレーションは

さすがに時間が足りないっぽい（制約：1 <= n <= 10^5 ）

どうしたものか？

考えてみると、「長方形の縦と横の長さの差の絶対値」を小さくするために

余りを大きくするのは意味がないことに気づく

例えば、3枚タイルがあったとして、1枚タイルを使用して2枚余らせるのも

2枚タイルを使用して1枚余らせるのも結果は同じだからだ

一辺が 2 以上のパターンになると

余らせるタイルを減らした方が最小値に近づく

（例えば6枚タイルがある場合、2 × 2 にするより、2 × 3 にした方がいい）

以上より、タイルを使い切る方針で、作れる長方形を列挙していく

提出したコード

# 入力
n=int(input())

# 最小値を保存する変数
# （n以下にはならないのでnで初期化しておく）
mn=n

# 一辺が 1〜n の長方形を列挙していく
for x in range(1,n+1):
  # もう一辺の長さ
  y=n//x

  # 余ったタイル
  a=n%x

  # 長方形の縦と横の長さの差の絶対値と
  # 余ったタイルの枚数の和の最小
  b=abs(y-x)+a

  # 最小値の更新
  mn=min(mn,b)

# 出力
print(mn)

提出結果はACでした

解説スライドだとなんだか難しいことを言っている…

興味のある人は読んでみてください

AtCoder Beginner Contest 040 解説