概要

\(N\) 個の商品から何個か選んで、合計金額がちょうど \(K\) 円になる方法の数を求める「部分和問題の数え上げ」です。

考察

問題の本質

この問題は、各商品を「選ぶ」か「選ばない」かの2択を繰り返し、選んだ商品の価格の合計がちょうど \(K\) になる組み合わせを数える問題です。

素朴なアプローチとその問題点

全ての商品について「選ぶ/選ばない」を試すと、\(2^N\) 通りの組み合わせを調べる必要があります。\(N = 100\) の場合、\(2^{100}\) は天文学的な数字となり、到底間に合いません（TLE）。

解決策：動的計画法（DP）

「合計金額が \(j\) 円になる方法の数」を効率的に計算するため、動的計画法を使います。

具体例で考えてみましょう。商品の価格が \([2, 3, 5]\)、\(K = 5\) の場合：

1. 初期状態: 何も買わないとき、合計 \(0\) 円になる方法は \(1\) 通り
2. 商品1（価格2円）を考慮後: 合計 \(0\) 円が \(1\) 通り、合計 \(2\) 円が \(1\) 通り
3. 商品2（価格3円）を考慮後: 合計 \(0, 2, 3, 5\) 円がそれぞれ \(1\) 通り
4. 商品3（価格5円）を考慮後: 合計 \(5\) 円は \(2\) 通り（\(\{3, 2\}\) と \(\{5\}\)）

このように、商品を1つずつ追加しながら、各金額に到達する方法の数を更新していきます。

アルゴリズム

0-1ナップサック型の部分和DP を使用します。

1. 配列 \(dp[j]\) を用意し、\(dp[j]\) = 「合計がちょうど \(j\) 円になる方法の数」とする
2. 初期値として \(dp[0] = 1\)（何も買わない方法は1通り）
3. 各商品 \(i\)（価格 \(H_i\)）について：
   • \(j = K\) から \(j = H_i\) まで逆順にループ
   • \(dp[j] \leftarrow dp[j] + dp[j - H_i]\)（商品 \(i\) を買う場合を追加）
4. 最終的に \(dp[K]\) が答え

なぜ逆順に更新するのか？

各商品は最大1個しか買えないため、同じ商品を複数回使わないようにする必要があります。

• 順方向（\(j\) を小さい方から大きい方へ） で更新すると、更新済みの \(dp[j - H_i]\) を参照してしまい、同じ商品を複数回使った場合も数えてしまいます。
• 逆方向（\(j\) を大きい方から小さい方へ） で更新すると、まだ今回の商品で更新されていない値を参照するため、各商品を最大1回だけ使うことが保証されます。

計算量

• 時間計算量: \(O(NK)\)
  • \(N\) 個の商品それぞれについて、最大 \(K\) 回の更新を行う
• 空間計算量: \(O(K)\)
  • 1次元配列 \(dp\) のみを使用

実装のポイント

• MOD演算を忘れない: 方法の数は非常に大きくなる可能性があるため、加算のたびに \(10^9 + 7\) で割った余りを取る

• 逆順ループの範囲: range(K, price - 1, -1) とすることで、\(j \geq H_i\) の範囲のみを更新（\(j < H_i\) では商品を買えないため）

• 初期値の設定: \(dp[0] = 1\) を忘れると、全ての値が \(0\) のままになってしまう

  ソースコード

def solve():
    MOD = 10**9 + 7
    
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    # dp[j] = 合計がちょうどj円になる購入方法の数
    dp = [0] * (K + 1)
    dp[0] = 1  # 何も買わない方法は1通り
    
    # 各商品について、選ぶか選ばないかを考える（部分和問題）
    for i in range(N):
        price = H[i]
        # 逆順に更新することで、各商品を最大1回だけ使うことを保証
        for j in range(K, price - 1, -1):
            dp[j] = (dp[j] + dp[j - price]) % MOD
    
    print(dp[K])

solve()

---

この解説は claude4.5opus によって生成されました。