概要

\(N\) 品の料理から任意の組み合わせを選び、おいしさの合計からこってり度の超過ペナルティを引いた「満足度」を最大化する問題です。\(N \leq 19\) という制約から、全ての組み合わせを列挙（ビット全探索）して解きます。

考察

問題の整理

選んだ料理の集合を \(S\) とすると、満足度は次の式で決まります：

\[\text{満足度} = \sum_{i \in S} A_i - D \times \max\!\left(0,\ \sum_{i \in S} B_i - K\right)\]

おいしさの合計が大きい料理を選びたいですが、こってり度の合計が \(K\) を超えると \(D\) の割合でペナルティがかかるため、単純に「おいしい料理を全部選ぶ」が最適とは限りません。

なぜ貪欲法が使えないか

• おいしさだけでソートして選ぶと、こってり度のペナルティを見落とします。
• こってり度を考慮した「コスパ」でソートしても、ペナルティは合計が \(K\) を超えた分にしかかからないため、閾値を境に状況が変わり、貪欲法では正しい答えが得られません。

\(N \leq 19\) がヒント

\(N\) が最大でも \(19\) なので、料理の選び方は全部で \(2^{19} = 524{,}288\) 通りしかありません。これなら全ての組み合わせを調べ上げることが可能です。

アルゴリズム

ビット全探索（ビットマスク列挙） を使います。

1. \(0\) から \(2^N - 1\) までの整数 \(\text{mask}\) を順に見ます。
2. \(\text{mask}\) の第 \(i\) ビットが \(1\) なら「\(i\) 番目の料理を注文する」と解釈します。
3. 各 \(\text{mask}\) に対して、選んだ料理のおいしさの合計 \(sa\) とこってり度の合計 \(sb\) を計算します。
4. 満足度 \(sa - D \times \max(0, sb - K)\) を求め、最大値を更新します。
5. 何も注文しない場合（\(\text{mask} = 0\)）の満足度は \(0\) なので、初期値を \(0\) にしておきます。

具体例: \(N = 3\) のとき、\(\text{mask} = 5 = (101)_2\) は「料理 \(0\) と料理 \(2\) を注文する」を意味します。

mask (2進)	選ぶ料理
000	なし
001	料理0
010	料理1
011	料理0, 1
100	料理2
101	料理0, 2
110	料理1, 2
111	料理0, 1, 2

計算量

• 時間計算量: \(O(N \cdot 2^N)\)
  • \(2^N\) 通りの部分集合それぞれに対して、\(N\) ビットを走査して合計を計算します。
  • \(N = 19\) のとき約 \(19 \times 524{,}288 \approx 10^7\) 回の演算で、十分高速です。
• 空間計算量: \(O(N)\)
  • 料理の情報を保持する配列のみ必要です。

実装のポイント

• 初期値を \(0\) にする: 何も注文しない場合の満足度が \(0\) なので、best = 0 で初期化します。これにより、全ての組み合わせが負の満足度になる場合でも正しく \(0\) が出力されます。

• ビット演算 mask & (1 << i): \(\text{mask}\) の第 \(i\) ビットが立っているかの判定です。これにより各料理を選ぶ・選ばないを効率的に管理できます。

• sys.stdin.read() による高速入力: Python では入力が多い場合に input() を繰り返すより、一括読み込みの方が高速です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    A = []
    B = []
    for i in range(N):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        A.append(a)
        B.append(b)
    
    best = 0  # 何も注文しない場合は0
    for mask in range(1, 1 << N):
        sa = 0
        sb = 0
        for i in range(N):
            if mask & (1 << i):
                sa += A[i]
                sb += B[i]
        val = sa - D * max(0, sb - K)
        if val > best:
            best = val
    
    print(best)

main()

---

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