あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC169 F - Knapsack for All Subsets

競プロ

問題原文

解法

$A$ → $A$ に部分集合 $T$ → $T$ の部分集合 $U$ みたいな構造をしている。

$dp[i\rbrack[j\rbrack :=$ $i$ 番目までみて $U$ として選んだものの総和が $S$ になるような通り数
とする。

ある $A_i$ に着目した時、遷移先は

$T$ として選ばない
$T$ としては選ぶが $U$ としては選ばない
$U$ として選ぶ

の３つがある。

実装

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i, a in enumerate(A):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= MOD
        if j + a <= S:
            dp[i + 1][j + a] += dp[i][j]
            dp[i + 1][j + a] %= MOD

print(dp[-1][-1] % MOD)

感想

解けなかったけど大変ためになった。すごい典型っぽい。
なんだろう、新しい視点を手に入れた感じ。
成長した〜wって感じがする（単純）