くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 144 C - Walk on Multiplication Table

Python3で解く AtCoder Beginner Contest 144 C - Walk on Multiplication Table

AtCoder 対称性 ABC-C

このコンテストのA, Bは九九の問題であった。この問題はそれを制約の範囲でかなり大きい表をイメージする。

{\displaystyle N}が{\displaystyle 10^{12}}と大きいので工夫して探索

概要

問題

  1. 九九のように{\displaystyle i \times j}のマスがある。
  2. そのマスの値は{\displaystyle i \times j}である。
  3. 2以上の1つ整数{\displaystyle N}を与える。
  4. {\displaystyle i = 1, j = 1}のマスからその値のマスに最小のステップで移動したい。
  5. 最小のステップ数は？

解くときに考えた内容

  • {\displaystyle i \times j}の結果が同じになったときが存在する。例えば{\displaystyle 24}を与えられたら、以下のようなパターンがある。

    {\displaystyle 1 \times 24}
    {\displaystyle 2 \times 12}
    {\displaystyle 3 \times 8}
    {\displaystyle 4 \times 6}

  • もちろん、{\displaystyle 6 \times 4}のような組も考えられるが探索範囲を限るために{\displaystyle i \leqq j} として、探索は{\displaystyle \sqrt{N}}までの範囲で、ステップ数{\displaystyle i + j - 2}の最小値を求めればいい。

    • 実装上は{\displaystyle \sqrt{N}}までの範囲の探索はいろんなやり方がある。
      1. 初期値{\displaystyle i}を適当に決めて、while i*i <= n:とするのが感覚的にわかりやすいと思う。
      2. 他にもfor i in range(2, int(-(-n**0.5//1))+1):などとする方法もあるけどぱっと見よくわからないのであまり使わない。

  • 実際には、{\displaystyle N}が{\displaystyle i}で割り切れる場合は、{\displaystyle N \div i = j}として、都度{\displaystyle i + j - 2}とその時までの最小値minvと比較して小さい方を新たにminvなどとすればいい

コード

def main():
    n = int(input())
    i = 2
    minv = int(10**12)
    while i*i <= n:
        if n % i == 0:
            a = i
            b = int(n / i)
            minv = min(minv, a+b-2)
        i += 1
    if minv < int(10**12):
        print(minv)
    else:
        print(n-1)

if __name__ == '__main__':
    main()