Atcoder ABC169 A-DをPythonで解く

4完。Eは20分ほど考えてまったくわからず。FはTLEでした。

A Multiplication 1

コメント：特になし

# ABC169 A Multiplication 1

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

print(a*b)

B Multiplication 2

コメント：はじめは、全て計算していたが、TLEになったため、途中でbreakさせる方法に変更。

# ABC169 B Multiplication 2

from collections import deque

n = int(input())

a_list = [int(x) for x in input().split()]

if min(a_list) == 0:
    print("0")
else:
    a_dq = deque(a_list)
    ans = 1
    for i in range(n):
        ans *= a_dq.popleft()
        if ans > 10**18:
            break

    if ans > 10**18:
        print("-1")
    else:
        print(ans)

C Multiplication 3

コメント：予想通りだったが、floatでそのまま計算すると、WAになったのでいったん整数で計算する方法に変更。

# ABC169 C Multiplication 3

a, b = map(lambda x: int(x.replace(".","")), input().split())

print(a*b//100)

D Div Game

コメント：素因数分解するだけ。

# ABC169 D Div Game

n = int(input())

def factorization(n):
    arr = []
    if n == 1:
        return 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

f_list = factorization(n)
ans = 0

for i in range(len(f_list)):
    _tmp = f_list[i][1]
    j = 1
    while _tmp >= 0:
        _tmp -= j
        j += 1
    ans += j-2

print(ans)

F Knapsack for All Subsets(TLE)

コメント：$S$を構成する要素数とパターン数を保持したかったので、dict型を使ったがTLEになった。

# ABC169 F Knapsack for All Subsets

from collections import deque
from collections import Counter

def merge_dict_add_values(d1, d2):
    return dict(Counter(d1) + Counter(d2))

n, s = map(int, input().split())
a_dq = deque([int(x) for x in input().split()])

dp = [[{0:0}] * (s+1) for _ in range(n+1)]
dp[0][0] = {0:1}

for i in range(n):
    _tmp = a_dq.popleft()
    for j in range(s+1):
        if j-_tmp < 0:
            dp[i+1][j] = dp[i][j]
        else:
            _tmp_d = dp[i][j-_tmp]
            _dict = dict()
            for k in _tmp_d.keys():
                _dict[k+1] = _tmp_d[k]
            dp[i+1][j] = merge_dict_add_values(dp[i][j],_dict)

# print(dp[n][s])
ans = 0
for k in dp[n][s].keys():
    v = dp[n][s][k]
    ans += (2**(n-k)) * v

print(ans%998244353)