概要

予算 \(K\) 以下で買える商品の選び方のうち、合計金額が最大になる値（\(K\) に最も近い値）を求めます。
これは「部分和問題（subset sum）」の典型で、到達可能な合計金額をDPで管理します。

考察

重要な気づき

「いくつかの商品を選ぶ」という条件は、各商品を 選ぶ/選ばない の2択なので、合計金額として「どの値が作れるか」を管理すればよいです。
つまり、「合計 \(s\) 円が作れるか？」を \(s=0..K\) の範囲で判定できれば、最後に \(K\) から下へ探して最大の到達可能値が答えになります。

素朴な方法がダメな理由

• 全探索：\(2^N\) 通りの選び方があり、\(N \le 100\) では到底間に合いません。
• 通常のDP（配列で \(dp[s]\) を持つ）：\(O(NK)\) で今回は \(100 \times 10^4 = 10^6\) 程度なので十分間に合いますが、Pythonではさらに高速に書ける方法があります。

どう解決するか

到達可能な合計 \(s\) を ビット列で表します。 - ビット列 bits の \(s\) ビット目が 1 ⇔ 合計 \(s\) が作れる - 商品価格 \(c\) を追加すると、到達可能集合は bits | (bits << c) で更新できる
（「今作れる合計に \(c\) を足したもの」＝左シフトで表現できるため）

この方法は、Pythonの多倍長整数のビット演算で高速に処理できます。

アルゴリズム

1. bits = 1 とする（\(0\) 円は必ず作れるので、0ビット目を1にする）。
2. 各商品価格 \(c\) について：
   • もし \(c > K\) なら、予算内の合計には寄与しないので無視してよい。
   • bits |= (bits << c) として到達可能な合計を更新する。
   • ただし \(K\) を超えるビットは不要なので、mask = (1 << (K+1)) - 1 を使って bits &= mask で \(0..K\) の範囲に切り詰める。
3. 最後に bits のうち立っているビットの最大位置が答え。
   • bits.bit_length() - 1 は「最上位の1ビットの位置」を返すので、それが最大の到達可能合計になる（マスク済みなので必ず \(\le K\)）。

具体例

\(K=7\), 商品が \([3,5]\) のとき： - 初期：bits は合計0のみ可能 → ...0001 - \(c=3\)： - bits<<3 は合計3が可能を表す → ...1000 - ORすると合計0,3が可能 → ...1001 - \(c=5\)： - bits<<5 は合計5,8が可能だが、\(8\) は不要（マスクで消える） - ORすると合計0,3,5が可能 → 最大は5

計算量

• 時間計算量: おおむね \(O\!\left(N \cdot \frac{K}{w}\right)\)
  （\(w\) は機械語ワード幅。ビット演算は「\(K\) ビットぶん」をまとめて処理するため高速）
• 空間計算量: \(O(K)\)（\(K+1\) ビットぶんの情報を保持）

実装のポイント

• mask = (1 << (K + 1)) - 1 で \(0..K\) のビットだけ残すのが重要です（これをしないと bits がどんどん巨大になり遅くなります）。

• \(c > K\) の商品は、どのみち予算内の合計には使えないのでスキップできます。

• 答えは bits.bit_length() - 1 で取得できます（マスク済みなので必ず \(K\) 以下）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    C = data[2:2+N]

    bits = 1  # sum 0 is possible
    mask = (1 << (K + 1)) - 1
    for c in C:
        if c <= K:
            bits |= (bits << c)
            bits &= mask

    print(bits.bit_length() - 1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。