概要

青木君がちょうど \(K\) 件をキャンセルして高橋君の最大利益を最小化する、という「最小化（青木）→最大化（高橋）」の問題です。\(N \le 8\) と小さいので、キャンセル集合・実行集合をビット全探索して答えを求めます。

考察

重要な観察

• 高橋君が選ぶべき依頼集合は「互いに時間帯が重ならない（両立する）」必要があります。つまり、選んだ集合が 衝突（重なり）を一切含まない ことが条件です。
• 青木君は「キャンセル後に高橋君が最適に動く」ことを見越しているので、最終的に求めたい値は
  [ \min{\text{キャンセル集合 }C,\ |C|=K}\ \max{\text{実行集合 }S\subseteq \overline{C},\ S\text{は両立}}\ \sum_{i\in S}V_i ] という min-max になります。

素朴なアプローチ

• 青木君のキャンセル候補は \(\binom{N}{K}\) 通り、高橋君の選び方は \(2^{N-K}\) 通りあります。
• しかし \(N \le 8\) なので、最悪でも \(2^N \times 2^N = 4^N = 65536\) 程度で十分間に合います（高速化の工夫が少しあれば余裕）。

どう解決するか

• 依頼集合をビットマスク（長さ \(N\) の 0/1）で表します。
• まず「ある集合が両立しているか？」を毎回区間同士でチェックすると面倒なので、衝突関係をビットで前計算します。
• さらに、全ての部分集合について
  • 報酬合計 val_sum[mask]
  • 両立しているか valid[mask]

を前計算しておくと、各キャンセル集合に対して「残った中での最大報酬」をすぐ探索できます。

アルゴリズム

1. 依頼同士の衝突をビットで持つ

依頼 \(i\) と \(j\) が重なる条件は、両立条件の否定で [ \neg(R_i \le L_j \ \text{or}\ R_j \le L_i) ] です。重なるなら conflict[i] の \(j\) ビットを立てます。

2. 全部分集合の「合計値」と「両立性」を DP 的に前計算

mask の最下位ビット（lsb）を 1 個取り出して、その要素を \(i\) とします。

• rest = mask ^ lsb（\(i\) を除いた集合）
• 報酬合計： [ \text{val_sum}[mask] = \text{val_sum}[rest] + V_i ]
• 両立性：
  • rest 自体が両立していて
  • i が rest のどれとも衝突しない（rest & conflict[i] == 0）

なら valid[mask] = True とできます。

これにより「集合が両立か？」を \(O(1)\) で参照できます。

3. 青木君のキャンセル集合を全探索し、そのときの高橋君の最適値を求める

• cancel を \(0\) から \(2^N-1\) まで全探索し、cancel.bit_count() == K のものだけ採用。
• remaining = all_mask ^ cancel が残った依頼集合。
• 高橋君は remaining の部分集合 subset のうち、
  • subset が remaining に含まれる：(subset & ~remaining) == 0
  • valid[subset] == True

を満たすものの val_sum[subset] 最大値を取ります。 - その最大値を best として、青木君はそれを最小化したいので ans = min(ans, best)。

計算量

• 時間計算量:
  
  • 衝突前計算 \(O(N^2)\)
    
  • 全部分集合の前計算 \(O(2^N)\)
    
  • キャンセル全探索 \(O(2^N)\)、各キャンセルで部分集合探索 \(O(2^N)\)
    よって合計
    [ O(N^2 + 4^N) ] （\(N \le 8\) なので十分高速）
• 空間計算量:
  [ O(2^N) ] （val_sum, valid など）

実装のポイント

• 区間は半開区間 \([L_i, R_i)\) なので、例えば \(R_i = L_j\) のときは重ならず両立します。衝突判定は not (R[i] <= L[j] or R[j] <= L[i]) の形にすると安全です。

• 「集合が残り集合に含まれるか」の判定は、ビット演算で
  subset & ~remaining == 0
  と書くのが簡潔です。

• valid[mask] を「1 要素追加」で作ると、両立性判定を毎回 \(O(N^2)\) せずに済みます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    L = [0] * N
    R = [0] * N
    V = [0] * N
    for i in range(N):
        L[i], R[i], V[i] = map(int, input().split())

    conflict = [0] * N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if not (R[i] <= L[j] or R[j] <= L[i]):
                conflict[i] |= 1 << j

    M = 1 << N
    val_sum = [0] * M
    valid = [False] * M
    valid[0] = True

    for mask in range(1, M):
        lsb = mask & -mask
        i = (lsb.bit_length() - 1)
        rest = mask ^ lsb
        val_sum[mask] = val_sum[rest] + V[i]
        valid[mask] = valid[rest] and ((rest & conflict[i]) == 0)

    all_mask = M - 1
    ans = 10**18
    for cancel in range(M):
        if cancel.bit_count() != K:
            continue
        remaining = all_mask ^ cancel
        best = 0
        for subset in range(M):
            if (subset & ~remaining) == 0 and valid[subset]:
                s = val_sum[subset]
                if s > best:
                    best = s
        if best < ans:
            ans = best

    print(ans)

if __name__ == "__main__":
    main()

---

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