1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

ABC144 C - Walk on Multiplication Table から学んだ

Last updated at Posted at 2021-09-21

abc144_1.png
abc144_2.png
abc144_3.png
abc144_4.png

う、掛け算表が分からない。。ググると。どうやら以下のイメージらしい。

150616timestable_top-w960.jpg

問題文に、一応掛け算表の定義が書いてある。なるほど。。

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
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?