概要

\(N\) 種類の花から \(K\) 種類以下を選ぶときの、「美しさの合計 ＋ 賞金の合計」の最大値を求める問題です。制約が \(N \le 15\) と非常に小さいため、bit全探索を用いてすべての選び方を試すことで正解を導くことができます。

考察

どの花を選ぶか・選ばないかの組み合わせは、花が \(N\) 種類あるため \(2^N\) 通り存在します。 通常、組み合わせの数が膨大になるとすべてのパターンを試すことはできませんが、本問題では \(N \le 15\) という制約が与えられています。\(N = 15\) の場合でも \(2^{15} = 32768\) 通りしかなく、全探索を行っても十分に高速に計算できます。

各選び方に対して、以下の手順でスコアを計算します。 1. 選んだ花の数が \(K\) 種類以下かを確認する。 2. 選んだ花の美しさの合計を計算する。 3. 各コンテストについて、参加条件を満たしているか（指定された範囲の花が1つでも含まれているか）を確認し、満たしていれば賞金を足す。

何も選ばない場合のスコアは \(0\) となるため、最大値の初期値を \(0\) として、全パターンのスコアの最大値を求めればよいことになります。

アルゴリズム

bit全探索という手法を使用します。これは、整数の2進数表現を利用して「選ぶ・選ばない」の組み合わせをすべて列挙する方法です。

1. \(0\) から \(2^N - 1\) までの整数 bits をループで回します。bits の \(i\) ビット目が \(1\) なら「花 \(i\) を選ぶ」、\(0\) なら「選ばない」と対応させます。
2. bits に含まれる \(1\) の数（選んだ花の数）を数え、これが \(K\) を超えている場合は条件を満たさないためスキップします。
3. 選んだ花の美しさ \(S_i\) を合計します。
4. コンテストの参加条件の判定を行います。
   • コンテスト \(j\) の条件「花 \(L_j\) から \(R_j\) のうち少なくとも \(1\) つ選ぶ」は、あらかじめその範囲のビットを \(1\) にした「ビットマスク」を作成しておくことで簡単に判定できます。
   • 選び方を表す bits と、コンテストの条件を表す mask の論理積（AND演算 bits & mask）を取り、結果が \(1\) 以上であれば「条件の範囲内の花が少なくとも \(1\) つ選ばれている」と判定できます。
5. 条件を満たしたコンテストの賞金 \(P_j\) を合計スコアに加算します。
6. 計算した合計スコアで、最大値 ans を更新します。

計算量

• 時間計算量: \(O(2^N \cdot (N + M))\)
  • 花の選び方が \(2^N\) 通りあります。
  • 各選び方に対して、選んだ花の確認に \(O(N)\)、コンテストの条件判定に \(O(M)\) の時間がかかります。
  • \(N, M \le 15\) のとき、全体で \(32768 \times 30 \approx 10^6\) 回程度の演算となり、実行時間制限（通常2秒）に余裕で間に合います。
• 空間計算量: \(O(N + M)\)
  • 花の美しさのリストや、コンテストの条件（ビットマスクと賞金）を保持するために使用するメモリ量です。

実装のポイント

• 0-indexed（0始まり）への変換 入力で与えられる花の番号は \(1\) から \(N\) ですが、プログラム（配列やビットシフト）で扱いやすくするために、すべて \(1\) を引いて \(0\) から \(N-1\) のインデックスに変換しています（L = int(...) - 1 など）。

• ビットマスクの作成 コンテストの条件範囲 \([L, R]\) を表すビットマスクは ((1 << (R - L + 1)) - 1) << L で作成できます。 例えば \(L=1, R=3\) の場合、範囲の長さは \(3\) なので 1 << 3 で \(8\)（2進数 1000）となり、そこから \(1\) を引くと \(7\)（2進数 0111）になります。これを \(L\)（\(=1\)）ビット左にシフトすることで、目的のマスク 1110 が完成します。

• 立っているビットのカウント Pythonでは、整数を2進数の文字列に変換する bin() メソッドと、文字を数える count() メソッドを組み合わせて bin(bits).count('1') と書くことで、選んだ花の数を簡潔に取得できます。

  ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    
    S = [int(x) for x in data[3:3+N]]
    
    contests = []
    idx = 3 + N
    for _ in range(M):
        L = int(data[idx]) - 1
        R = int(data[idx+1]) - 1
        P = int(data[idx+2])
        mask = ((1 << (R - L + 1)) - 1) << L
        contests.append((mask, P))
        idx += 3
        
    ans = 0
    
    for bits in range(1 << N):
        if bin(bits).count('1') > K:
            continue
            
        score = 0
        for i in range(N):
            if (bits >> i) & 1:
                score += S[i]
                
        for mask, P in contests:
            if bits & mask:
                score += P
                
        if score > ans:
            ans = score
            
    print(ans)

if __name__ == '__main__':
    main()

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