ABC144 C - Walk on Multiplication Table から学んだ
6282 ワード
う、掛け算表が分からない。。ググると。どうやら以下のイメージらしい。
問題文に、一応掛け算表の定義が書いてある。なるほど。。
N へのアクセスアプローチから最小のモノを答えよ。。的な。
なるほど、ざくっと書いたら通った。
WalkonMultiplicationTable.py
N = int(input())
lis = []
from math import *
for n in range(1,floor(isqrt(N))+1):# 10^12 まで試す必要ない 10^6 で充分
if N%n == 0:
lis.append([n,N//n])
#print(lis)
ans = float("inf")
for a,b in lis:
ans = min(ans,a-1 +b-1)
print(ans)
#144ms
幅優先探索が使えるかとワクワクしたが、そこまで必要なかった。
step1.N を 2 つの要素に分解,組み合わせをリストする。
step2.組み合わせの中から、最短ルートを探す
10^12 ではなく、10^6 までで充分な理由は以下で触れてます。
さっぱり忘れて解き直し。
横移動、下移動 の差分を最小にすると移動距離は最小になると思った。
abc144c.py
N = int(input())
lis = []
from math import floor
for i in range(1,floor(N**0.5)+1):
if N%i == 0:
lis.append([i,N//i,abs(i-N//i)])#[下移動、横移動、下-横] を一パックにして lis に格納
lis = sorted(lis,key=lambda t:t[2]) #lis[2] 下-横の値で sort
#print(lis)
print(lis[0][0]-1+lis[0][1]-1) #lis[0] を呼び出して答えを導出
#133ms
Author And Source
この問題について(ABC144 C - Walk on Multiplication Table から学んだ), 我々は、より多くの情報をここで見つけました https://qiita.com/AKpirion/items/f819afa4f6e088731831著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .