AtCoder Beginner Contest 144「C - Walk on Multiplication Table」（Ruby）

平方根の活用がポイント

問題

問題文 高橋君は無限に広い掛け算表の上にいます。

掛け算表のマス ( i , j ) には整数 i × j が書かれており、高橋君は最初 ( 1 , 1 ) にいます。

高橋君は 1 回の移動で ( i , j ) から ( i + 1 , j ) か ( i , j + 1 ) のどちらかにのみ移ることができます。

整数 N が与えられるので、 N が書かれているマスに到達するまでに必要な移動回数の最小値を求めてください。

制約 2 ≤ N ≤ 10 12 N は整数である。

atcoder.jp

考えたこと

1回の移動で (i,j) から (i+1,j) か(i,j+1)とあることから、縦方向か横方向に、それぞれ１マスづつしか動けないことが分かります。

現在地が（1, 1）なので、移動先が１であれば、移動する必要はありません。

つまり移動回数は、(i - 1) + (j - 1)で求めることが出来ます。

そして整数 i×jは、複数の組み合わせが想定されます。

移動回数がiとjの足し算なので、移動回数の最小値を求めるには、出来るだけ互いの値を小さく抑える必要があります。

マスの位置は掛け算で表されるので、どちらかの値を１にして、一方を最大の値にすれば、移動回数も最大になります。

互いの値の差が最大の時に移動回数が最大になるので、互いの値の差が最小になるケースを考える必要があります。

互いの値の差が最小になるので、両方の値が同じ場合です。

平方根（）を用いれば、互いの値の差が無い数値を求めることが出来ます。

しかしNは整数なので、平方根の結果が整数にならない場合は、そこから最も違い数値を探す必要があります。

通りなので、全探索でも対応出来そうです。

コード

n = gets.to_i
a = Math.sqrt(n).to_i

while n % a != 0
  a -= 1
end

b = n / a
puts a + b - 2

コード長 100 Byte
実行時間 45 ms
メモリ 3836 KB