ABC169 復習

今回はC問題まで解けました。ただ、WAとTLEを合わせて4回出たのが悔しいです。
D問題については、素因数分解について学ぶことができたのでまぁ良しとしましょう。

A - Multiplication 1

掛け算の問題ですね。
単純に入力値をかけ合わせれば答えとなります。

a, b =map(int, input().split())
print(a * b)

B - Multiplication 2

全ての値をかけ合わせればよいだけですが、以下の条件に当てはまる場合を考慮します。

1. 10¹⁸を超える場合
2. 積が0になる場合

なお、サンプルケースにあるように0が最後の入力である場合についても注意が必要です。

n = int(input())
a = list(map(int, input().split()))

INF = 10 ** 18
ans = 1
# 0が1つでもあれば積は0になるので
if any([n == 0 for n in a]):
    print(0)
    exit()

# あとは単純に積を計算するだけ
for n in a:
    ans *= n
    # INFを超えればその時点で終了
    if ans > INF:
        ans = -1
        break
print(ans)

C - Multiplication 3

問題としては極単純な問題でしたね。
ただし、小数計算のために答えが誤る場合があります。小数の計算についての知識を問われているような問題でした。
pythonを使っているなら、Decimalを使いましょう。小数が出てきたら何も考えずにDecimalを使いましょう。
（大事なことなので2回言いました。）

import math
from decimal import Decimal

a, b = map(Decimal, input().split())
ans = a * b
print(int(ans))

D - Div Game

解けませんでした。
どうやら素因数分解をすればよいそうです。 例えば、N=24の場合、素因数分解をすると2³ * 3¹になります。
さらに、各指数（この場合３と１）について、値を引いていく操作が割る操作と同じになります。 *1
ただし問題の制約上、同じ数で割ることができないため、1を引く、2を引く・・という具合に引いていくことになります。

import math

#素因数分解
def prime_factorization(N):

    n = N
    sqrt = int(math.sqrt(n)) + 1
    m = {}
    for i in range(2, sqrt):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n /= i
            m[i] = cnt

    # nが1になっていなければn自体が素数
    if n != 1:
        m[n] = 1

    return m

n = int(input())
m = prime_factorization(n)
ans = 0

#各指数を回す
for v in m.values():
    b = 1
    #指数を順に1引く、2引く・・としていく（これが割る操作と同様になる）
    while v - b >= 0:
        ans += 1
        v -= b
        b += 1

print(ans)

今回はここまで。
WAの影響でパフォーマンスも大したことにならないと思いましたが、これでもパフォーマンスが711出ていたのが驚きです。
レーティングもちょびっと（12）上がりました。
緑への道のりはまだまだ続く・・・。

*1:例えば、2³/2¹ = 2² となるため、指数部に着目すると減算をしていることと同じになります。