概要

花の種類数 \(N\) が最大15種類と小さいため、花の選び方を全て試すビット全探索で解くことができる問題です。

考察

問題では、花を最大 \(K\) 種類まで選び、その美しさの合計と、選んだ花によって参加できるコンテストの賞金の合計を最大化する必要があります。コンテストの参加条件は、特定の区間 \([L_j, R_j]\) 内の花が少なくとも1つ選ばれていることです。

\(N\) と \(M\) の制約が最大15と小さいため、花の選び方（\(2^N\) 通り）を全て試すことができます。各選び方について、選んだ花の美しさの合計と、コンテストの参加条件を満たすかどうかを確認して賞金を加算すれば、最大値を求めることができます。

アルゴリズム

1. 花の選び方をビットマスクで表現し、\(0\) から \(2^N - 1\) まで全て試します。
2. 各ビットマスクについて、選んだ花の数が \(K\) 以下か確認します。
3. 選んだ花の美しさの合計を計算します。
4. 各コンテストについて、区間 \([L_j, R_j]\) 内に選ばれた花が1つでもあるか確認します。あれば、そのコンテストの賞金 \(P_j\) を加算します。
5. 美しさの合計と賞金の合計の和を計算し、最大値を更新します。

計算量

• 時間計算量: \(O(2^N \times M \times N)\)
  • ビットマスクの数が \(2^N\)、各ビットマスクに対して \(M\) 個のコンテストをチェックし、各コンテストの区間の長さは最大 \(N\) です。
• 空間計算量: \(O(N + M)\)
  • 入力データを格納するためのメモリです。

実装のポイント

• ビットマスクの各ビットが花の選択に対応します。ビットが立っている場合、その花を選んだことを意味します。

• コンテストの区間は0-indexedに調整して扱います。

• 花を1つも選ばない場合（ビットマスクが0）も考慮します。この場合、美しさの合計と賞金の合計は0になります。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    idx = 0
    N = int(data[idx]); K = int(data[idx+1]); M = int(data[idx+2]); idx += 3
    S = list(map(int, data[idx:idx+N])); idx += N
    contests = []
    for i in range(M):
        L = int(data[idx]); R = int(data[idx+1]); P = int(data[idx+2]); idx += 3
        contests.append((L-1, R-1, P))  # 0-indexedに調整
    
    ans = 0
    # すべての花の選び方（ビットマスク）を試す
    for bitmask in range(1 << N):
        count = bin(bitmask).count('1')
        if count > K:
            continue
            
        total_s = 0
        # 美しさの合計を計算
        for i in range(N):
            if bitmask & (1 << i):
                total_s += S[i]
                
        total_p = 0
        # 各コンテストについて参加条件を満たすかチェック
        for (L, R, P) in contests:
            found = False
            for i in range(L, R+1):
                if bitmask & (1 << i):
                    found = True
                    break
            if found:
                total_p += P
                
        total = total_s + total_p
        if total > ans:
            ans = total
            
    print(ans)

if __name__ == '__main__':
    main()

この解説は deepseekv3 によって生成されました。