概要

イベントの依頼の中から青木君が \(K\) 件キャンセルし、残った中で高橋君が時間帯が重ならないように選んで報酬を最大化するとき、青木君の最適戦略における高橋君の最小報酬を求める問題。

考察

この問題は、まず「青木君がキャンセルする \(K\) 件を選ぶ」→「高橋君が残った中から両立するものを選んで報酬を最大化する」という2段階の最適化が必要です。

重要な観察

• \(N \leq 8\) と非常に小さいので、青木君がキャンセルする \(K\) 件の選び方は全部で \(\binom{N}{K}\) 通りあり、これは高々 \(\binom{8}{4} = 70\) 程度なので全探索可能です。
• 各キャンセル後のケースについて、高橋君の最適な選び方は「区間スケジューリング問題」の亜種であり、区間が重ならないように選んで報酬の合計を最大化する必要があります。

素朴なアプローチの問題点

もし青木君がランダムにキャンセルしても、高橋君が最適に選ぶことで高い報酬を得られる可能性があります。青木君の目的は「高橋君が得る報酬を最小にする」ことです。そのため、青木君はすべてのキャンセル候補について試し、それぞれに対する高橋君の最大報酬を計算し、その中の最小値を選ぶ必要があります。

解決方法

1. すべての \(\binom{N}{K}\) 通りのキャンセル方法を列挙（itertools.combinations を使う）
2. 各ケースについて、残ったイベントに対して区間スケジューリング的なDPを行う
3. DPでは、ビットマスクを使って「どのイベントを選んだか」を状態として管理する（ビットDP）

アルゴリズム

1. キャンセルの全探索

   • combinations(range(N), K) でキャンセルする \(K\) 件の組み合わせを生成します。

2. 残ったイベントでの最大報酬計算

   • 残ったイベントを開始時間順にソートします（スケジューリングしやすくするため）。
   • ビットDPを使います：
     • dp[mask] := ビットマスク mask で表されるイベント集合を選んだときの最大報酬
     • 初期値：dp[0] = 0（何も選んでいない状態）
     • 更新：

          - 現在の状態 `mask` に対して、まだ使っていないイベント $i$ を追加しようとする
          - そのイベントが既存のイベントと時間帯が被らないかを確認
          - 被らなければ、`dp[mask | (1 << i)]` を更新
       

3. 全体の最小値を記録

   • 各キャンセルパターンでの最大報酬の最小値が答え

計算量

• キャンセルの組み合わせ数：\(\binom{N}{K} \leq \binom{8}{4} = 70\)
• 各ケースでのビットDPの状態数：\(2^N \leq 256\)
• 各状態から次の遷移：\(O(N)\)
• よって、時間計算量は \(O\left(\binom{N}{K} \cdot 2^N \cdot N\right)\)
• 空間計算量は主にDPテーブルによるもので、\(O(2^N)\)

具体的には： - 時間計算量: \(O\left(\binom{N}{K} \cdot N \cdot 2^N\right)\) - 空間計算量: \(O(2^N)\)

実装のポイント

• イベントの時間帯の重なり判定は、区間 \([L_i, R_i)\) と \([L_j, R_j)\) が重なるかどうかを以下のように判定します：

  
  not (r_j <= l_i or r_i <= l_j)
  

  これにより、端点が一致する場合は重ならないとみなされます（問題文の定義に合う）。

• ビットDPの際に、mask に含まれるイベントと新しく追加するイベントとの間に衝突がないかを毎回確認する必要があります。

• 最終的な答えは、各キャンセルパターンにおける「最大報酬」の最小値です。

  ソースコード

from itertools import combinations

def solve():
    N, K = map(int, input().split())
    events = []
    for i in range(N):
        L, R, V = map(int, input().split())
        events.append((L, R, V, i))
    
    # 青木君がキャンセルするK件の組み合わせを全探索
    min_reward = float('inf')
    
    for cancel_indices in combinations(range(N), K):
        # 残ったイベント
        remaining_events = [events[i] for i in range(N) if i not in cancel_indices]
        
        # 残ったイベントのインデックス（元のインデックス）
        n_rem = len(remaining_events)
        if n_rem == 0:
            max_reward = 0
        else:
            # dp[i][j][k] := i番目まで見て、最後に選んだイベントがjで、選んだ集合がk（ビットマスク）
            # 今回はN<=8なので、ビットマスクを使って全選択状態を管理可能
            
            # 各イベントをソートしておけばDPしやすい
            # (開始時間, 終了時間, 報酬, 元のindex)
            remaining_events.sort()
            
            # ビットDPで最大報酬を求める
            # dp[mask] := maskで表されるイベント集合を選んだときの最大報酬
            dp = {}
            dp[0] = 0
            max_state = 1 << n_rem
            
            for mask in range(max_state):
                if mask not in dp:
                    continue
                current_value = dp[mask]
                
                for i in range(n_rem):
                    if (mask >> i) & 1:
                        continue  # すでに選ばれている
                    
                    # 新たにイベントiを選ぶ
                    new_mask = mask | (1 << i)
                    l_i, r_i, v_i, _ = remaining_events[i]
                    
                    # 競合するイベントがないかチェック
                    conflict = False
                    for j in range(n_rem):
                        if (mask >> j) & 1:
                            l_j, r_j, v_j, _ = remaining_events[j]
                            # 区間が重なるか？
                            if not (r_j <= l_i or r_i <= l_j):
                                conflict = True
                                break
                    if not conflict:
                        if new_mask not in dp:
                            dp[new_mask] = 0
                        dp[new_mask] = max(dp[new_mask], current_value + v_i)
            
            max_reward = max(dp.values())
        
        min_reward = min(min_reward, max_reward)
    
    print(min_reward)

solve()

この解説は qwen3-coder-480b によって生成されました。