ABC144 C - Walk on Multiplication Table

AtCoder Python3

備忘録

問題

atcoder.jp

回答.1 (遅い)

import sys
import os
 
 
def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")
 
    N = int(sys.stdin.readline().rstrip())
 
    ret = float('inf')
    for i in range(1, 10000000):
        q, mod = divmod(N, i)
        if mod == 0:
            j = N // i
            ret = min(ret, ((j-1)+(i-1)))
 
    print(ret)
 
 
if __name__ == '__main__':
    main()

考え方

Nの最大値は10^12なので、1から最大10^7までforでiを回し、
iで割り切ることが出来るかつ、最小となるiとjを探索した。
純粋なi * jの掛け算のため、最大値を10^7した理由は下記の2点。

  • 最大値の半分まで探索すればいいこと
  • O(N^7)程度ならLTEにならないと思ったこと

結果の実行時間は1963 msと、ギリギリだが何とかACにはなる。

回答.2 (早い)

import sys
import os
import math
 
def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")
 
    N = int(sys.stdin.readline().rstrip())
 
    max = int(math.sqrt(N) + 1)
    ret = float('inf')
    for i in range(1, max):
        q, mod = divmod(N, i)
        if mod == 0:
            j = N // i
            ret = min(ret, ((j-1)+(i-1)))
 
    print(ret)
 
 
if __name__ == '__main__':
    main()

考え方

公式解説を見て改善。
回答.1 に加えて、探索範囲を1から最大√Nに絞って全探索を行う。
Nを求めることが出来るi * jでiまたはjの最大値は√N以下であることは自明なので、
無駄に最大値を10^7にする必要がなく実行時間も202 ms程度に収まった。

回答.3

Submission #8149895 - AtCoder Beginner Contest 144

iを1≦i*i≦Nの範囲で探索されている方。
掛け算の性質をよく理解されていて、コードも簡潔で勉強になった。