Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、14問目を解説していきたいと思います。
問題名 【C – Digits in Multiplication】
入力
N：整数
考察
今回、A x B = N となる A,Bを全列挙し、その中で条件に対し、最適なものを出力すれば行けます。
A x B = N の全列挙のやり方
今回、N < 10^10 なので、Nについてfor文を回すとTLEしてしまいます。
#だめな例
box = []
for i in range(N):
if N % i == 0:
box.append([i, N//i])しかし、よくよく考えてみると、N以下の数について全列挙する必要はありません。なぜならN = 6のときの約数の組み合わせは(1,6),(2,3),(3,2),(6,1)ですが、(1,6) == (6,1) , (2,3) == (3,2)なので後半2つはいりません。
このことを理解すれば、全探索しなければならない範囲は、1から√Nの範囲であることがわかります。(A*B == N となるA,Bは必ずどちらかは√N以下になるため)
なのでこちらの方法で A x B = N となるA,B を列挙します。列挙後、条件を満たすA,Bのうち最適な答えを出力します。
POINT1 全探索する範囲について考える
ちなみに、今回はAとBの差が小さいのが最適な答えになります。なぜなら AとBの差が小さいということはそれだけ2つの数の桁数が近いということです。今回AとBは反比例の関係にあるので、A と Bができる限り近い数のほうが良いからです。
POINT2 AとBの関係は反比例
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = II()
#N = A*Bとなるような A*Bの列挙
def koukan(n):
ret = []
for i in range(1, int(n ** (1 / 2)) + 1):
if n%i ==0:
ret.append((i,n//i))
flg = n//i
if flg <= i:
break
return ret
a = koukan(N)
b,c = a[-1][0],a[-1][1]
print(max(len(str(b)),len(str(c))))まとめ
こーゆー問題は、解いてて楽しいです。
コメント