概要

花を最大 \(K\) 種類まで選ぶとき、選んだ花の美しさ合計と、条件（区間内に1つでも選ばれている）を満たすコンテストの賞金合計の最大値を求めます。
\(N \le 15\) と小さいので、花の選び方をビット集合（部分集合）として全探索します。

考察

重要な気づき

• 「花を選ぶ/選ばない」は各花について二択なので、選び方は全部で \(2^N\) 通りあります。
• \(N \le 15\) なので \(2^{15}=32768\) と小さく、全ての部分集合を列挙して評価しても十分間に合います。
• 各コンテスト \(j\) は「区間 \([L_j, R_j]\) のどれか1つでも選ばれていれば賞金 \(P_j\)」という条件です。
  これは (選んだ集合) と (区間に含まれる花の集合) が共通要素を持つか、つまりビット演算で
  • 条件成立 \(\Leftrightarrow\) mask & cmask != 0 と判定できます。

素朴にやると何がまずいか

• 例えば各部分集合ごとに「美しさの合計」を毎回 \(N\) 個走査して足すと、全体で \(O(2^N \cdot N)\) になります。これは今回でも間に合いますが、より高速にする工夫として 部分集合DPで美しさ合計を使い回すと実装がきれいになります。
• コンテスト判定も、区間を毎回 \([L,R]\) で走査すると無駄が出ます。区間をあらかじめビットマスクにしておけば、判定は1回の & で終わります。

どう解決するか

• 花の集合を長さ \(N\) のビットマスク mask（\(i\) 番目のビットが 1 なら花 \(i\) を選ぶ）で表す。
• 各コンテストの区間 \([L_j, R_j]\) もビットマスク cmask に変換しておく。
• mask について
  • 選んだ個数が \(K\) 以下なら（mask.bit_count() <= K）
  • 美しさ合計 + 条件を満たすコンテスト賞金合計 を計算して最大を更新する。

（例）\(N=5\) で花 {2,4} を選ぶなら mask = 01010(2)。
コンテスト区間が \([3,5]\) なら cmask = 11100(2)。
このとき mask & cmask = 01000(2) で 0 ではないので条件成立、賞金を加算できます。

アルゴリズム

1. 入力を受け取る。
2. 各コンテスト \(j\) について、区間 \([L_j, R_j]\) をビットマスク cmask に変換して (cmask, P_j) として保存する。
3. 全ての部分集合 mask = 0 .. 2^N-1 について美しさ合計 beauty[mask] を前計算する。
   • mask の最下位の 1 ビット lsb を取り出し、そのビットが表す花 \(i\) を足すことで
     \(beauty[mask] = beauty[mask \setminus \{i\}] + S_i\)
     を使う（コードでは beauty[mask ^ lsb] + S[i]）。
4. 全ての mask を列挙し、選んだ花の数が \(K\) を超えるものは除外する。
5. total = beauty[mask] とし、全コンテストについて
   • もし mask & cmask != 0 なら total += P
6. total の最大値を答えとして出力する。

計算量

• 時間計算量:
  美しさ前計算が \(O(2^N)\)、各部分集合でコンテスト判定が \(O(M)\) なので全体で
  \(O(2^N \cdot M + 2^N) = O(2^N \cdot M)\)
• 空間計算量:
  美しさ配列 beauty が \(O(2^N)\)、コンテスト保存が \(O(M)\) なので
  \(O(2^N)\)

実装のポイント

• 区間 \([L, R]\) をビットマスク化すると、条件判定が mask & cmask の1回で済みます。

• mask.bit_count()（Python 3.8+）で選択数を高速に数えられます。

• 美しさ合計の前計算は、毎回 \(N\) 個足し直すよりも lsb を使った更新（部分集合DP）が簡潔です。

• 「何も選ばない（mask=0）」も許され、その場合の値は 0 なので、答えの初期値を 0 にしておけば自然に扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K, M = map(int, input().split())
    S = list(map(int, input().split()))
    contests = []
    for _ in range(M):
        L, R, P = map(int, input().split())
        mask = 0
        for i in range(L - 1, R):
            mask |= 1 << i
        contests.append((mask, P))

    size = 1 << N
    beauty = [0] * size
    for mask in range(1, size):
        lsb = mask & -mask
        i = lsb.bit_length() - 1
        beauty[mask] = beauty[mask ^ lsb] + S[i]

    ans = 0
    for mask in range(size):
        if mask.bit_count() > K:
            continue
        total = beauty[mask]
        for cmask, p in contests:
            if mask & cmask:
                total += p
        if total > ans:
            ans = total

    print(ans)

if __name__ == "__main__":
    main()

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