Résoudre Atcoder ABC169 A-D avec Python

4 terminé. E pense environ 20 minutes et ne comprend pas du tout. F était TLE.

A Multiplication 1 Commentaire: rien de particulier

# ABC169 A Multiplication 1

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

print(a*b)

B Multiplication 2 Commentaire: Au début, j'ai tout calculé, mais depuis qu'il est devenu "TLE", j'ai changé la méthode pour le faire "casser" au milieu.

# 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 Commentaire: Comme prévu, lorsque je l'ai calculé tel quel avec float, il est devenu WA, donc j'ai changé une fois la méthode de calcul avec un entier.

# ABC169 C Multiplication 3

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

print(a*b//100)

D Div Game Commentaire: Factorisez simplement.

# 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) Commentaire: J'ai utilisé dict type parce que je voulais garder le nombre d'éléments et de motifs qui composent $ S $, mais il est devenu 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)