概要

\(N\) 個のアイテムからいくつかを選び、その合計金額をちょうど \(K\) 円にする組み合わせの数を求める問題です。これは「部分和問題」と呼ばれる有名な問題の一種であり、動的計画法（DP）を用いることで効率的に解くことができます。

考察

1. 全探索の限界

最も単純な方法は、各商品について「買う」か「買わない」かの2通りをすべて試すことです。しかし、商品の数が \(N\) 個あるとき、組み合わせの総数は \(2^N\) 通りとなります。 本問題では \(N \le 100\) であるため、\(2^{100} \approx 1.26 \times 10^{30}\) となり、制限時間内に計算を終えることは不可能です。

2. 動的計画法（DP）への変換

「現在の合計金額」に着目すると、同じ金額になる組み合わせが何度も現れることに気づきます。そこで、以下の状態を定義して計算を効率化します。

dp[i][j]：\(i\) 番目までの商品を使って、合計金額を \(j\) 円にする方法の数

\(i\) 番目の商品（価格 \(H_i\)）を考えるとき、状態は以下のように遷移します。 - \(i\) 番目の商品を買わない場合: 合計金額は変わらないため、dp[i-1][j] 通りのままです。 - \(i\) 番目の商品を買う場合: 合計金額が \(H_i\) 増えて \(j\) 円になるので、その前段階は dp[i-1][j - H_i] 通りです（ただし \(j \ge H_i\) の場合）。

これらを足し合わせたものが dp[i][j] となります。

アルゴリズム

動的計画法（空間計算量の最適化）

上記の dp[i][j] をそのまま実装すると \(O(N \times K)\) のメモリが必要ですが、1次元配列 dp[j] を使い回すことで節約できます。

1. 配列 dp をサイズ \(K+1\) で用意し、0 で初期化します。
2. 何も選んでいない状態（合計 0 円）は 1 通りなので、dp[0] = 1 とします。
3. 各商品 \(H_i\) について、以下の処理を繰り返します。
   • 金額 \(j\) を \(K\) 円から \(H_i\) 円まで逆順に ループさせます。
   • dp[j] = (dp[j] + dp[j - H_i]) % mod と更新します。

なぜ逆順に更新するのか？ 正順（\(H_i\) から \(K\)）で更新してしまうと、同じ商品を何度も選んだ（重複使用した）結果が加算されてしまいます。後ろから更新することで、「まだ今回考慮している商品 \(H_i\) を選んでいない状態」の値を参照できるため、各商品を最大1回しか使わない条件を満たすことができます。

計算量

• 時間計算量: \(O(N \times K)\)
  • 商品の数 \(N\) と目標金額 \(K\) の二重ループになります。\(100 \times 10000 = 10^6\) 程度の計算量であり、制限時間内に十分間に合います。
• 空間計算量: \(O(K)\)
  • 1次元のDPテーブルのみを保持するため、非常に効率的です。

実装のポイント

• 余りを取るタイミング: 組み合わせの数は非常に大きくなる可能性があるため、加算するたびに \(10^9 + 7\) で割った余りを計算します。

• 初期化: dp[0] = 1 を忘れないようにしましょう。これは「何も選ばない」という 1 通りの方法を意味します。

• ループの範囲: Python の range(k, price - 1, -1) は \(K\) から price までの値を逆順に生成します。

  ソースコード

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    h = list(map(int, input_data[2:]))
    
    mod = 10**9 + 7
    
    # dp[j] は合計金額が j 円になる組み合わせの数
    dp = [0] * (k + 1)
    dp[0] = 1
    
    for price in h:
        # 重複して選ばないように、後ろから更新する
        for j in range(k, price - 1, -1):
            dp[j] = (dp[j] + dp[j - price]) % mod
            
    print(dp[k])

if __name__ == "__main__":
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。