AtCoder Beginner Contest 169 D を Python で

2020年6月1日

AtCoder Beginner Contest 169 D を Python で

お久しぶりです。タムくんです。少しモチベーションが下がってしまってコンテストをさぼっていたのですが,今回から再開して,また解説ブログも書いていきたいと思います。今回はまずAtCoder Beginner Contest 169 D を Python で解説していきます。続いてA~Cも書いていきますので,そちらもまた書いたらご覧ください。
それでは,まずは問題文から。


D – Div Game


実行時間制限: 2 sec / メモリ制限: 1024 MB×

配点 : 400 点

問題文

正の整数 N が与えられます。 N に対して、以下の操作を繰り返し行うことを考えます。

  • はじめに、以下の条件を全て満たす正の整数 z を選ぶ。
    • ある素数 p と正の整数 e を用いて、 z=p^e と表せる
    • N が z で割り切れる
    • 以前の操作で選んだどの整数とも異なる
  • N を、N/z に置き換える

最大で何回操作を行うことができるか求めてください。

制約

  • 入力はすべて整数である。
  • 1≤N≤10^12

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを整数として出力せよ。


入力例 1 

24

出力例 1

3

例えば、次のように操作を行うことで、 3 回操作を行うことができます。

  • z=2(=2^1) とする。( 操作後、N=12 となる。)
  • z=3(=3^1) とする。( 操作後、 N=4 となる。 )
  • z=4(=2^2) とする。( 操作後、 N=1 となる。 )

入力例 2 

1

出力例 2

0

一度も操作を行うことができません。


入力例 3

64

出力例 3 

3

例えば、次のように操作を行うことで、 33 回操作を行うことができます。

  • z=2(=2^1) とする。( 操作後、 N=32 となる。)
  • z=4(=2^2) とする。( 操作後、 N=8 となる。 )
  • z=8(=2^3) とする。( 操作後、 N=1 となる。 )

入力例 4

1000000007

出力例 4

1

例えば、次のように操作を行うことで、 1 回操作を行うことができます。

  • z=1000000007(=1000000007^1) とする。( 操作後、 N=1 となる。 )

入力例 5

997764507000

出力例 5

7


解説

問題文を一言で言うと,N を素数の異なるべき乗で何回割れるかというような問題です。これはまず N を素因数分解すると見通しがつきます。とりあえず入力例1の n=24 の場合で考えてみると,
24 = 2^3 + 3^1 と因数分解できます。
こうすることで,今回割れる素数は 2と3 であることが分かります。

では,このときある整数 e を用いて何回 p^e の形を作って N を割れるか,と言うものですが,これは e を1から順番に見ていけばいいです。24の場合は,例えばまず割りたい素数を2としたときには

  • 24 ÷ 2^1 = 12
  • 12 ÷ 2^2 = 3

となり,これ以上素数2のべき乗(次は2^3)で割れないから,これで終わりです。
今度は素数3でも同じことをして,1回しか割れないから,結局24の場合は2+1=3を出力すればいいことになります。

64の場合も同様です。素因数分解すると
64 = 2^6 ですから,これは2だけで割ればよくて,

  • 64 ÷ 2^1 = 32
  • 32 ÷ 2^2 = 8
  • 8 ÷ 2^3 = 1

となり,以上で出力は3です。

実際考えるときは N を割っていきましたが,素因数分解しているのでわざわざ N を割って考える必要はありません。素因数分解するときに出てきた素数のべき乗について,それぞれ
-1, -2, -3 ・・・
と順々に引いていって,0以上になるという条件の下で最大何回引けるか確認します。

例えば 3456 = 2^7 * 3^3 であれば,まず素数2について見ると

  • 7 – 1 = 6
  • 6 – 2 = 4
  • 4 – 3 = 1
  • 1 – 4 = -3 ←これはアウト

ですから,3回操作を行えて,素数3の時は

  • 3 -1 = 2
  • 2 – 2 = 0
  • 0 – 3 = -3 ←これはアウト

となり,2回操作を行えて,結局合計5回操作を行えることになります。実際のコーディングの際はこのように操作する回数を計算することになります。

では,コーディングに移ります。素因数分解はPythonで高速素因数分解〜競プロ用〜の記事を参考にさせていただきました。このコードによって,例えば24なら,

factorization(24)
// [[2, 3], [3, 1]]

というように素因数分解してくれます。これを用いて,for文を利用し,[i][1]の値を-1,-2,・・・とした結果,0以上になるという条件の下で何回引けるかという値を count に格納していきます。自分のコードでは,a を素因数分解したときの値を入れるリストとし,b を先ほど述べた for 文の中で,-1, -2, ・・・と引いていく数に対応させます。
素因数分解したときに出てくる素数pによって,Nは少なくとも p^1で一回は割れるので,まずそれぞれの素数に対して,count に1を足して,次にp^2,p^3・・・で割れるかというような判断をしています。

注意したいのは N=1 の場合で,この場合に限り1度も割れないので,これだけ別枠で0を出力するようにしています。

それでは解答例に移ります。

解答例

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
 
n = int(input())
 
count = 0
a = factorization(n)
if n == 1:
  print(0)
  exit()
  
for i in range(len(a)):
  a[i][1] -= 1
  count += 1
  b = 2
  while a[i][1] > 0:
    a[i][1] -= b
    if a[i][1] >= 0:
      count += 1
    b += 1
 
print(count)

いかがだったでしょうか。久しぶりに解説ブログを上げたのでなかなか書くのが難しいなと思いましたが,もし分からないところや間違っていると思われるところがあれば,気軽にtwitterで教えてください。

それでは!

他の問題も解説しているので,ぜひ見ていってください!
ABC 169 A
ABC 169 B
ABC 169 D