概要

\(N\) 件のイベント依頼から青木君がちょうど \(K\) 件をキャンセルし、残りから高橋君が時間帯の重ならない依頼を選んで報酬を最大化する、という二人のミニマックス問題です。青木君は高橋君の最終報酬を最小化するようにキャンセルを選びます。

考察

問題の構造

この問題は 二段階の最適化 になっています。

1. 青木君（外側）: \(N\) 件からちょうど \(K\) 件を選んでキャンセル → 高橋君の報酬を 最小化
2. 高橋君（内側）: 残った \(N - K\) 件から、互いに時間帯が重ならない依頼を選ぶ → 報酬を 最大化

制約に注目

\(N \leq 8\) と非常に小さいです。これにより：

• 青木君がキャンセルする \(K\) 件の選び方は高々 \(\binom{8}{K} \leq \binom{8}{4} = 70\) 通り
• 残った \(N - K\) 件から高橋君が選ぶ部分集合は高々 \(2^{8} = 256\) 通り

すべてを全探索しても十分間に合います。

なぜ全探索で良いか

一般的な重み付き区間スケジューリング問題はDPで \(O(N \log N)\) で解けますが、今回は青木君の妨害という外側の最適化が加わっています。\(N\) が大きければ高度なアルゴリズムが必要ですが、\(N \leq 8\) なので素朴な全列挙で十分です。

アルゴリズム

1. 青木君のキャンセルを列挙: \(N\) 件から \(K\) 件を選ぶ全ての組み合わせを combinations で列挙する。

2. 各キャンセルパターンに対して高橋君の最適解を計算: 残った依頼の全部分集合（ビットマスクで列挙）について、選んだ依頼が 全てペアごとに両立する（時間帯が重ならない）かを確認し、条件を満たす中で報酬合計が最大のものを求める。

   • 依頼 \(i\) と \(j\) が両立する条件: \(R_i \leq L_j\) または \(R_j \leq L_i\)（半開区間なので端点が一致してもOK）

3. 最小値を取る: 全キャンセルパターンに対する高橋君の最適報酬のうち、最小値 が答え。

具体例

例えば \(N=3, K=1\) で依頼が \([0,5), [3,8), [5,10)\)（報酬はそれぞれ \(10, 20, 15\)）の場合：

• 依頼1をキャンセル → 残り \(\{2,3\}\): 重なるので片方だけ選び、最大 \(20\)
• 依頼2をキャンセル → 残り \(\{1,3\}\): 両立するので両方選び、\(10+15=25\)
• 依頼3をキャンセル → 残り \(\{1,2\}\): 重なるので片方だけ選び、最大 \(20\)

青木君は最小の \(20\) を狙うので、答えは \(20\)。

計算量

• 時間計算量: \(O\left(\binom{N}{K} \cdot 2^{N-K} \cdot (N-K)^2\right)\)
  • キャンセルの列挙が \(\binom{N}{K}\) 通り、各パターンで部分集合を \(2^{N-K}\) 個列挙し、各部分集合でペアごとの両立判定に \((N-K)^2\)
  • \(N \leq 8\) なので最大でも \(70 \times 256 \times 64 \approx 10^6\) 程度で十分高速
• 空間計算量: \(O(N)\)（イベント情報の保持のみ）

実装のポイント

• \(K \geq N\) の場合: 全依頼がキャンセルされるので答えは \(0\)。先に処理しておくとよい。

• 両立判定: 半開区間 \([L, R)\) なので、\(R_i = L_j\) のときは重ならない（両立する）。条件を R_i <= L_j or R_j <= L_i と書く（等号を含める）ことに注意。

• ビットマスクによる部分集合列挙: \(N\) が小さいので、各ビットが「その依頼を選ぶか」に対応させて \(0\) から \(2^n - 1\) まで回すだけで全部分集合を列挙できる。

  ソースコード

import sys
from itertools import combinations

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    events = []
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        events.append((L, R, V))
    
    # For a given set of available events (as a list of indices), compute max weighted interval scheduling
    def max_reward(available):
        n = len(available)
        if n == 0:
            return 0
        # Bitmask DP over subsets of available events
        # Check compatibility and find max weight independent set on interval graph
        # Since n <= 8, we can enumerate all 2^n subsets
        best = 0
        for mask in range(1 << n):
            # Check if all selected events are pairwise compatible
            selected = []
            total = 0
            for j in range(n):
                if mask & (1 << j):
                    selected.append(available[j])
                    total += events[available[j]][2]
            # Check pairwise compatibility
            valid = True
            for a in range(len(selected)):
                for b in range(a + 1, len(selected)):
                    ia = selected[a]
                    ib = selected[b]
                    # They overlap if NOT (R_ia <= L_ib or R_ib <= L_ia)
                    if not (events[ia][1] <= events[ib][0] or events[ib][1] <= events[ia][0]):
                        valid = False
                        break
                if not valid:
                    break
            if valid:
                best = max(best, total)
        return best
    
    all_indices = list(range(N))
    
    if K >= N:
        print(0)
        return
    
    # Blue: enumerate all ways to cancel exactly K events
    # For each cancellation, compute Takahashi's optimal reward
    # Blue picks the cancellation that minimizes this
    min_reward = float('inf')
    
    for cancel in combinations(all_indices, K):
        cancel_set = set(cancel)
        remaining = [i for i in all_indices if i not in cancel_set]
        reward = max_reward(remaining)
        min_reward = min(min_reward, reward)
    
    print(min_reward)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。