概要

イベントの開催依頼がN件あり、ライバル会社がK件をキャンセルした後、残った依頼から時間が重ならないように選んで報酬の合計を最大化する問題です。

考察

制約条件がN≤8と小さいため、キャンセルするK件の組み合わせを全探索することができます。各キャンセルパターンについて、残った依頼から最適な選択を行う必要があります。イベントスケジューリング問題の典型的な解法として、終了時刻でソートした後、動的計画法（DP）を用いて最大報酬を計算します。

アルゴリズム

1. キャンセルするK件の組み合わせを全探索します
2. 各組み合わせについて、残った依頼を終了時刻の昇順にソートします
3. DPテーブルdp[t]を用意し、時刻tまでに得られる最大報酬を保持します
4. 各時刻tについて、前の時刻からの値を引き継ぎます
5. 終了時刻がtの依頼について、開始時刻LでのDP値に報酬Vを加算した値でDP[t]を更新します
6. 全キャンセルパターンにおける最小の最大報酬を答えとします

計算量

• 時間計算量: \(O(2^N \cdot N \cdot T)\) （Tは最大時刻）
• 空間計算量: \(O(N + T)\)

実装のポイント

• キャンセル組み合わせの生成にはitertools.combinationsを使用

• 残った依頼は終了時刻でソートして処理

• DP更新時は、同じ終了時刻の依頼をまとめて処理

• 最大時刻は入力から動的に計算

  ソースコード

import itertools

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0]); k = int(data[1])
    events = []
    index = 2
    max_time = 0
    for i in range(n):
        L = int(data[index]); R = int(data[index+1]); V = int(data[index+2])
        index += 3
        events.append((L, R, V))
        if R > max_time:
            max_time = R
            
    # すべてのキャンセル組み合わせを生成
    indices = list(range(n))
    ans = 10**9
    # K個キャンセルする全ての組み合わせ
    for cancel_set in itertools.combinations(indices, k):
        remaining = []
        for i in range(n):
            if i not in cancel_set:
                remaining.append(events[i])
        # 残った依頼を終了時刻でソート
        remaining.sort(key=lambda x: x[1])
        dp = [0] * (max_time+1)
        # DP: 時刻0から最大時刻まで
        t_index = 0
        for t in range(1, max_time+1):
            dp[t] = dp[t-1]
            while t_index < len(remaining) and remaining[t_index][1] == t:
                L, R, V = remaining[t_index]
                if dp[L] + V > dp[t]:
                    dp[t] = dp[L] + V
                t_index += 1
        total_reward = dp[max_time]
        if total_reward < ans:
            ans = total_reward
            
    print(ans)

if __name__ == "__main__":
    main()

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