問題

お気持ち

一番の鍵は$i \neq j \Rightarrow a_i \neq a_j$っぽい
もし同じものを使えるなら、Xの分割数として$ \lbrace 1,1,…,1,1 \rbrace $でいいじゃんね、みたいな話になると思われるので…。
$i \neq j \Rightarrow a_i \neq a_j$なので、全ての数字は1回だけ、使うor使わないの選択が出来る
- つまり、ナップザックDP…！！！
1~N個の商品があって、ナップザックの容量はNで、重さはそれぞれ1~Nで…
- 価値は、その数字の正の約数の個数$=d(x)$

ソースコード

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())

d = dict()

for i in range(1, N + 1):
    if i == 1:
        d[1] = 1
        continue

    tmp = factorization(i)
    score = 1
    for k, v in tmp:
        score *= (v + 1)
    d[i] = score

prev_dp = [-1] * (N + 5)
prev_dp[0] = 0

for next_num in range(1, N + 1):
    fact_cnt = d[next_num]
    add_weight = next_num
    next_dp = [-1] * (N + 5)

    for now_weight in range(N + 1):
        if prev_dp[now_weight] == -1:
            continue

        # 選ばない場合
        next_dp[now_weight] = max(next_dp[now_weight], prev_dp[now_weight])

        if now_weight + add_weight <= N:
            next_dp[now_weight + add_weight] = max(next_dp[now_weight + add_weight], prev_dp[now_weight] + fact_cnt)
    prev_dp = next_dp
print(prev_dp[N])

スパークリング黒ココア/RWS 2022 5. Partition of N

問題

お気持ち

ソースコード