概要

この問題は、「\(N\) 個の料理からどれを選ぶか」という部分集合の最適化問題です。
\(N \le 19\) と小さいので、すべての選び方を全探索して最大満足度を求めれば十分間に合います。

考察

料理はそれぞれ「選ぶ / 選ばない」の 2 通りなので、選び方は全部で \(2^N\) 通りあります。

通常、このような問題では「組み合わせが多すぎるのでは？」と心配になりますが、今回は

• \(N \le 19\)
• よって \(2^{19} = 524288\)

しかありません。
50 万通り程度なら、各組み合わせについて合計を計算しても十分高速です。

重要な気づき

この問題で大事なのは、料理を選ぶ順番は関係なく、どの集合を選ぶかだけが重要ということです。
つまり、考えるべきなのは「部分集合」です。

ある部分集合を選んだとき、

• おいしさの合計を \(S_A\)
• こってり度の合計を \(S_B\)

とすると、満足度は

\[ S_A - D \times \max(0, S_B - K) \]

で求まります。

したがって、各部分集合について

1. \(S_A\) を求める
2. \(S_B\) を求める
3. 上の式で満足度を計算する
4. 最大値を更新する

という流れでよいです。

素朴なアプローチについて

この問題では、むしろ素朴な全探索が最適です。
たとえば「動的計画法を使わないといけないのでは？」と考えるかもしれませんが、

• \(K\) や \(B_i\) は最大 \(10^6\)
• こってり度の合計もかなり大きくなりうる

ので、こってり度を状態にした DP は重くなりがちです。

一方で \(N\) がとても小さいため、全探索のほうが簡単で確実です。

例

たとえば 3 品の料理があるとします。

• 料理 1: \((A_1, B_1) = (5, 3)\)
• 料理 2: \((A_2, B_2) = (4, 2)\)
• 料理 3: \((A_3, B_3) = (8, 7)\)
• \(K = 5, D = 2\)

料理 1 と 2 を選ぶと

• おいしさ合計 \(= 5 + 4 = 9\)
• こってり度合計 \(= 3 + 2 = 5\)

なので超過はなく、満足度は

\[ 9 - 2 \times \max(0, 5 - 5) = 9 \]

料理 1 と 3 を選ぶと

• おいしさ合計 \(= 5 + 8 = 13\)
• こってり度合計 \(= 3 + 7 = 10\)

なので超過は \(5\)、満足度は

\[ 13 - 2 \times 5 = 3 \]

このように、すべての組み合わせを比べれば最大値が求まります。

アルゴリズム

ビット全探索を行います。

各料理に対して

• ビットが \(1\) なら選ぶ
• ビットが \(0\) なら選ばない

と対応させます。

たとえば mask を \(0\) から \((1 \ll N) - 1\) まで動かすと、全部分集合を表せます。

手順

1. 答え ans を \(0\) で初期化する
   （何も注文しない選択肢があり、その満足度は \(0\)）
2. mask を \(0\) から \((1 \ll N)-1\) まで全探索する
3. 各 mask について、選ばれている料理の
   • おいしさ合計 sa
   • こってり度合計 sb を求める
4. 満足度 $\( \text{score} = sa - D \times \max(0, sb - K) \)$ を計算する
5. ans = max(ans, score) で更新する
6. 最後に ans を出力する

計算量

• 時間計算量: \(O(N \times 2^N)\)
• 空間計算量: \(O(N)\)

\(N = 19\) のときでも、

\[ 19 \times 2^{19} \approx 10^7 \]

程度なので、十分実行可能です。

実装のポイント

• 空集合（何も注文しない）も許されるので、答えは少なくとも \(0\) です。
  そのため ans = 0 で初期化しておくのが自然です。

• 部分集合の列挙にはビット演算を使います。
  if (mask >> i) & 1: で「\(i\) 番目の料理を選んでいるか」を判定できます。

• Python では整数が自動で多倍長になるため、合計値が大きくなっても特にオーバーフローを心配する必要はありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K, D = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    ans = 0
    for mask in range(1 << N):
        sa = 0
        sb = 0
        for i in range(N):
            if (mask >> i) & 1:
                sa += A[i]
                sb += B[i]
        score = sa - D * max(0, sb - K)
        if score > ans:
            ans = score

    print(ans)

if __name__ == "__main__":
    main()

---

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