概要

\(N\) 品の料理から任意の組み合わせを選び、特定の計算式で得られる「満足度」を最大化する問題です。料理の数 \(N\) が最大 19 と非常に小さいため、すべての組み合わせを調べる「全探索」が有効です。

考察

この問題のポイントは、「どの料理を選ぶか」の組み合わせが全部で何通りあるかを見積もることです。

各料理について「選ぶ」か「選ばない」かの 2 択があるため、料理が \(N\) 品あるとき、組み合わせの総数は \(2^N\) 通りとなります。 制約を確認すると \(N \le 19\) なので、組み合わせの数は最大でも \(2^{19} = 524,288\) 通りです。これはコンピュータにとっては十分に小さい数であり、すべての組み合わせについて満足度を計算しても制限時間内に間に合います。

満足度の計算式は以下の通りです： - こってり度の合計 \(S_B\) が \(K\) 以下のとき：満足度 = \(S_A\)（おいしさの合計） - こってり度の合計 \(S_B\) が \(K\) を超えるとき：満足度 = \(S_A - D \times (S_B - K)\)

すべての組み合わせを列挙し、それぞれについてこの式を適用して最大値を探せば答えが得られます。

アルゴリズム

すべての部分集合（組み合わせ）の和を効率よく求めるために、ビット全探索の考え方、あるいは動的計画法（集合の拡張）を用います。

1. 全組み合わせの列挙: 空のセット（何も注文しない状態：おいしさ合計 0、こってり度合計 0）から始めます。
2. 逐次追加: 1番目の料理を追加した状態、2番目の料理を追加した状態……と、1品ずつ「これまでのすべての組み合わせに対して、新しい料理を加えたパターン」を増やしていきます。
   • \(i\) 番目の料理（おいしさ \(A_i\)、こってり度 \(B_i\)）を考えるとき、それまでに作成したすべての組み合わせ（\(2^{i-1}\) 通り）に対して、この料理を加えた新しい組み合わせを作ります。
3. 満足度の計算: 各組み合わせについて、おいしさの合計 \(S_A\) とこってり度の合計 \(S_B\) から満足度を計算し、その最大値を保持します。

計算量

• 時間計算量: \(O(2^N)\) 料理を一品増やすごとに組み合わせの数が 2 倍になります。\(N=19\) のとき \(2^{19} \approx 5.2 \times 10^5\) 回の計算で済むため、高速に動作します。
• 空間計算量: \(O(2^N)\) すべての組み合わせの合計値をリストに保存する場合、\(2^N\) 個の要素を格納するメモリが必要です。\(N=19\) であれば数 MB 程度であり、問題ありません。

実装のポイント

提供されたコードでは、Python で高速に動作させるために以下の工夫がなされています。 - リスト内包表記とスライス: sums_A[bit : 2*bit] = [x + a for x in sums_A[:bit]] のように記述することで、Python の内部で最適化されたループが走り、個別に append するよりも高速にすべての組み合わせの和を計算できます。 - 一括計算: 各ビットマスク（\(0\) から \(2^N-1\) まで）をループで回して「どのビットが立っているか」を判定する \(O(N \cdot 2^N)\) の方法ではなく、上記のように前の結果を利用して \(O(2^N)\) で計算しています。これにより、実行時間を大幅に短縮しています。

ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 料理の数 N、上限 K、減少量 D を取得します
    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    
    # 各料理のおいしさ A とこってり度 B を格納するリストを作成します
    dishes_A = []
    dishes_B = []
    for i in range(N):
        dishes_A.append(int(input_data[3 + 2*i]))
        dishes_B.append(int(input_data[4 + 2*i]))
        
    # すべての料理の組み合わせ（2^N 通り）について、おいしさの合計とこってり度の合計を計算します
    # sums_A[i] は i 番目のビットマスクに対応する料理の組み合わせのおいしさの合計を保持します
    num_combinations = 1 << N
    sums_A = [0] * num_combinations
    sums_B = [0] * num_combinations
    
    # 動的計画法（集合の拡張）を用いて、すべての部分集合の和を効率的に計算します
    for i in range(N):
        a = dishes_A[i]
        b = dishes_B[i]
        bit = 1 << i
        # すでに計算された部分集合に現在の料理を加えた新しい部分集合を作成します
        # スライスとリスト内包表記を使用することで、Pythonでの実行速度を向上させます
        sums_A[bit : 2*bit] = [x + a for x in sums_A[:bit]]
        sums_B[bit : 2*bit] = [x + b for x in sums_B[:bit]]
        
    # 得られる満足度の最大値を求めます
    # 初期値は「1品も注文しない」場合の満足度である 0 です
    max_sat = 0
    for sa, sb in zip(sums_A, sums_B):
        # 満足度の計算式: (おいしさの合計) - D * max(0, こってり度の合計 - K)
        if sb > K:
            current_sat = sa - D * (sb - K)
        else:
            current_sat = sa
        
        # 最大値を更新します
        if current_sat > max_sat:
            max_sat = current_sat
            
    # 結果を出力します
    print(max_sat)

if __name__ == '__main__':
    solve()

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