概要

予算 \(K\) 円以内で、与えられた商品の価格の合計を最大化する問題です。これは「部分和問題」と呼ばれる典型的な動的計画法（DP）の問題であり、予算内での最適な組み合わせを効率的に探索する必要があります。

考察

1. 素直なアプローチ（全探索）

各商品について「買う」か「買わない」かの 2 択があるため、合計 \(2^N\) 通りの組み合わせが存在します。本問題では \(N \leq 100\) であるため、組み合わせの数は \(2^{100} \approx 1.26 \times 10^{30}\) となり、制限時間内にすべてを調べることは不可能です。

2. 動的計画法（DP）による解決

「ある金額 \(j\) を作ることが可能か？」という情報を保持しながら、商品を 1 つずつ追加していくことを考えます。 \(dp[j]\) を「合計金額 \(j\) を作れるなら真、そうでないなら偽」とする配列を用意すると、新しい商品の価格 \(C_i\) を追加するたびに、すでに作れる金額 \(j\) に対して \(j + C_i\) も作れるようになります。 予算 \(K\) までの範囲でこの更新を行うことで、計算量を \(O(NK)\) に抑えることができます。

3. ビットセットによる高速化

この DP は「ビット演算」を用いることでさらに高速化できます。 大きな整数を 1 つの「ビットの列」と見なし、その \(j\) 番目のビットが 1 であれば「金額 \(j\) が作れる」ことを表します。 新しい価格 \(c\) を追加する操作は、現在のビット列を \(c\) だけ左シフト（<< c）し、元のビット列と論理和（OR）を取る操作に対応します。Python は多倍長整数をサポートしているため、このビット演算を非常に簡潔かつ高速に行うことができます。

アルゴリズム

1. 初期化:
   • 合計 0 円は常に作れるため、reachable = 1（2進数で ...0001）とします。
   • 予算 \(K\) を超える金額を無視するため、下位 \(K+1\) ビットがすべて 1 であるマスクを用意します。
2. 更新:
   • 各商品の価格 \(c\) について、以下を繰り返します。
   • reachable |= (reachable << c)
   • 予算 \(K\) を超えるビットを消すため、マスクを適用します。
3. 答えの抽出:
   • reachable の中で最も上位にある 1 のビットの位置（インデックス）が、予算 \(K\) 以下の最大合計金額となります。
   • Python の bit_length() メソッドを使うと、「最も上位のビットが何番目か」を簡単に取得できます。

計算量

• 時間計算量: \(O(NK / w)\)
  • \(N\) は商品の個数、\(K\) は予算です。\(w\) は CPU のワードサイズ（Python の内部実装による最適化）に相当します。ビット演算を用いることで、通常のループによる DP よりも数十倍高速に動作します。
• 空間計算量: \(O(K)\)
  • 予算 \(K\) までの状態を保持するビット列（巨大な整数）を 1 つ保持するためのメモリが必要です。

実装のポイント

• ビット演算の活用: reachable |= (reachable << c) という 1 行で、それまでに作れたすべての金額に対して「新しい商品を追加する」という遷移をまとめて計算しています。

• 予算による制限: 商品を追加するたびに reachable &= mask を行うことで、予算 \(K\) を超える不要な情報を削ぎ落とし、数値が肥大化しすぎるのを防いでいます。

• 結果の取得: bit_length() - 1 は、その整数を 2 進数で表したときの最も左にある 1 の位置を返します。例えば reachable が 2 進数で 1010（10進数で 10）なら、bit_length() は 4 となり、作れる最大金額は \(4-1 = 3\) であることがわかります。

  ソースコード

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])
    c_list = list(map(int, input_data[2:]))
    
    # ビットセットを用いた動的計画法 (DP)
    # reachable の i 番目のビットが 1 ならば、合計金額 i が可能であることを示す
    reachable = 1
    
    # 予算 K を超えるビットを無視するためのマスク
    mask = (1 << (k + 1)) - 1
    
    for c in c_list:
        # 新しい商品 c を加える場合、現在の可能金額を c だけシフトして OR を取る
        reachable |= (reachable << c)
        # 予算 K を超える部分は不要なのでマスクする
        reachable &= mask
    
    # reachable の最も上位のビット（bit_length - 1）が K 以下の最大合計金額となる
    print(reachable.bit_length() - 1)

if __name__ == "__main__":
    solve()

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