概要

\(N\) 種類の花（\(N \leq 15\)）から \(K\) 種類以下を選び、花の美しさの合計とコンテスト賞金の合計の和を最大化する問題です。\(N\) が小さいため、花の選び方をすべて列挙（ビット全探索）することで解けます。

考察

重要な気づき

• \(N \leq 15\) という制約が非常に小さいです。花を選ぶ・選ばないの \(2\) 通りが \(N\) 種類分あるので、全部の組み合わせは \(2^{15} = 32768\) 通りしかありません。
• 各組み合わせに対して、美しさの合計とコンテスト賞金の合計を計算すればよいので、全列挙が十分間に合います。

コンテストの参加判定

コンテスト \(j\) に参加できる（＝参加しなければならない）条件は「番号 \(L_j\) 以上 \(R_j\) 以下の花を少なくとも \(1\) 種類植えていること」です。

例えば \(L_j = 2, R_j = 4\) なら、花 \(2, 3, 4\) のうちどれか \(1\) つでも選んでいれば参加条件を満たします。

この判定をビットマスクで効率よく行います。花 \(i\)（\(1\)-indexed）をビット \(i-1\) に対応させ、コンテスト \(j\) に対して \(L_j\) から \(R_j\) までのビットを立てたマスク contest_mask[j] を事前に作っておきます。選んだ花の集合 flower_set との AND を取り、\(0\) でなければ条件を満たしていると判定できます。

具体例

\(N = 3\), \(K = 2\), 花の美しさが \(S = [-5, 3, 2]\)、コンテスト \((L=1, R=2, P=10)\) の場合：

• 花 \(\{2, 3\}\) を選ぶ → ビット表現 110 → 美しさ \(3+2=5\)、コンテストは \(L=1, R=2\) のマスク 011 と AND すると `010 \neq 0\( なので参加 → 合計 \)5 + 10 = 15$
• 花 \(\{3\}\) だけ選ぶ → ビット表現 100 → 美しさ \(2\)、マスク 011 と AND すると `000 = 0\( なので不参加 → 合計 \)2$

アルゴリズム

1. 各コンテスト \(j\) について、\(L_j\) から \(R_j\) の花に対応するビットマスク contest_mask[j] を前計算する。
2. \(0\) から \(2^N - 1\) までのすべてのビットマスク flower_set を列挙する。
3. 各 flower_set について：
   • 立っているビットの数（選んだ花の種類数）が \(K\) 以下か確認する。超えていればスキップ。
   • 選んだ花の美しさの合計を計算する。
   • 各コンテストについて、flower_set & contest_mask[j] が \(0\) でなければ賞金 \(P_j\) を加算する。
   • 美しさ＋賞金の合計が最大値を更新するか確認する。
4. 最大値を出力する（\(1\) つも選ばない場合の \(0\) も候補に含める）。

計算量

• 時間計算量: \(O(2^N \times (N + M))\)
  • \(2^N\) 通りの部分集合を列挙し、各部分集合に対して \(N\) 個の花の美しさ計算と \(M\) 個のコンテスト判定を行います。\(N, M \leq 15\) なので \(32768 \times 30 \approx 10^6\) 程度で十分高速です。
• 空間計算量: \(O(N + M)\)

実装のポイント

• 花は 1-indexed で与えられますが、ビットマスクでは 0-indexed で管理するため、花 \(i\) をビット \(i-1\) に対応させる点に注意します。

• 何も選ばない場合（flower_set = 0）の合計値は \(0\) です。初期値を \(0\) にしておけば、すべての花の美しさが負でコンテスト賞金を考慮しても損する場合にも正しく \(0\) が出力されます。

• bin(flower_set).count('1') でビットの立っている数（popcount）を簡単に求められます。

  ソースコード

import sys
from itertools import combinations

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    S = [0] * N
    for i in range(N):
        S[i] = int(input_data[idx]); idx += 1
    
    contests = []
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        contests.append((L, R, P))
    
    # For each contest, precompute the bitmask of flowers that can satisfy it
    # Flower i (1-indexed) corresponds to bit (i-1)
    contest_mask = [0] * M
    for j in range(M):
        L, R, P = contests[j]
        mask = 0
        for i in range(L - 1, R):
            mask |= (1 << i)
        contest_mask[j] = mask
    
    best = 0  # choosing nothing gives 0
    
    # Enumerate all subsets of flowers with size <= K
    # N <= 15, so 2^15 = 32768 subsets
    for flower_set in range(1 << N):
        count = bin(flower_set).count('1')
        if count > K:
            continue
        
        # Sum of beauty
        beauty = 0
        for i in range(N):
            if flower_set & (1 << i):
                beauty += S[i]
        
        # Sum of contest prizes
        prize = 0
        for j in range(M):
            # Contest j is satisfied if flower_set has at least one flower in [L_j, R_j]
            if flower_set & contest_mask[j]:
                prize += contests[j][2]
        
        total = beauty + prize
        if total > best:
            best = total
    
    print(best)

main()

---

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