竸プロ精進記 ABC144 C – Walk on Multiplication Table python 3

問題:https://atcoder.jp/contests/abc144/tasks/abc144_c

無限に大きい掛け算九九の表のような座標テーブルで、あるNが与えられた時にNが書いてあるマスに移動するための最短経路を求める問題です。全探索してそれぞれのマス目がある位置を探して、その時々の原点からの距離を求めていき最短の経路を探します。全探索して探せば良いですが、Nが10^12とかなり大きいため、そのままやると計算時間が間に合わずTLEします。この場合、√Nだけ探索すれば十分です。N=a×b、a>bの時、a,bを入れ替えても求めたい経路の長さは変わらないので、√Nまでの数で全探索するだけで用が足りるからです。

√Nなら計算量は最大でも10^6なので十分間に合います。

コード例

import math
N=int(input())
lim=int(math.sqrt(N))
ans=10**13
for i in range(1,lim+1):
    if N%i==0:
        if ans>abs(i+(N//i)-2):
            ans=abs(i+(N//i)-2)
print(ans)

平方根を使うのでmathをimportします。答えを代入するansに十分大きい値を入れて初期化しておきます。

iを1〜√Nまでの範囲で全探索します。もしNをiで割り切れるのであれば、その時の商(N//i)とiとの和から2を引いたものが経路の長さになります。これがansより小さい値ならば更新していきます。

最後まで探索し終わったら最も小さい経路を出力すればOKです。

スポンサーリンク
スポンサーリンク




スポンサーリンク




シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク
スポンサーリンク