概要

複数のイベントの中から、時間が重ならないようにいくつか選んで、得られる「利得」を最大化する問題です。この問題は、数式を整理することで「重み付き区間スケジューリング問題」という典型的な動的計画法（DP）の形に帰着させることができます。

考察

1. 目的関数の整理

まず、最大化したい「利得」の式を整理しましょう。受理するイベントの集合を \(S\)、すべてのイベントの集合を \(T\) とします。 利得は以下の式で表されます： $\(\text{利得} = |S| \times B - \sum_{i \in T \setminus S} C_i\)$

ここで、\(\sum_{i \in T \setminus S} C_i\) （却下したイベントの補償費用の合計）は、次のように書き換えられます： $\(\sum_{i \in T \setminus S} C_i = \left( \sum_{i \in T} C_i \right) - \left( \sum_{i \in S} C_i \right)\)$

これを利得の式に代入すると： $\(\begin{aligned} \text{利得} &= |S| \times B - \left( \sum_{i \in T} C_i - \sum_{i \in S} C_i \right) \\ &= \sum_{i \in S} B + \sum_{i \in S} C_i - \sum_{i \in T} C_i \\ &= \sum_{i \in S} (B + C_i) - \sum_{i \in T} C_i \end{aligned}\)$

\(\sum_{i \in T} C_i\) は選ぶイベントに関わらず一定の値です。したがって、この問題を解くには、「各イベント \(i\) に重み \(W_i = B + C_i\) が設定されているとき、重なりがないようにイベントを選んで、その重みの総和 \(\sum_{i \in S} W_i\) を最大化する」という問題に変換できます。

2. 座標圧縮

イベントの開始時刻 \(L_i\) や終了時刻 \(R_i\) は最大で \(10^9\) と非常に大きいため、そのまま配列の添字として使うことはできません。しかし、実際に意味がある時刻は、各イベントの端点（\(L_i\) と \(R_i\)）として現れる高々 \(2N\) 個の値だけです。 そこで、出現するすべての時刻を昇順に並べて \(0, 1, 2, \dots\) と番号を振り直す座標圧縮を行うことで、計算可能な範囲に収めます。

3. 動的計画法（DP）

座標圧縮後の時刻を \(t_0, t_1, \dots, t_{M-1}\) とします。以下のDPを定義します。 - \(dp[i] = \) 時刻 \(t_i\) までに終了するイベントの中から、重なりなく選んだときの重みの最大合計

遷移は以下のようになります： 1. イベントを選ばない場合: \(dp[i] = dp[i-1]\) 2. 時刻 \(t_i\) で終了するイベント \(j\) を選ぶ場合: \(dp[i] = \max(dp[i], dp[\text{イベント } j \text{ の開始時刻のインデックス}] + W_j)\)

これを順番に計算することで、最終的な答えは \(dp[M-1] - \sum C_i\) となります。

アルゴリズム

1. 各イベント \(i\) について、重み \(W_i = B + C_i\) を計算する。
2. すべての \(L_i, R_i\) を集めて重複を除去し、ソートして座標圧縮用のマップを作成する。
3. 圧縮後の各終了時刻 \(R_i\) ごとに、その時刻で終わるイベントのリストを保持しておく。
4. DPテーブルを初期化し、時刻 \(0\) から順番に遷移を計算する。
5. 求まった最大値から、あらかじめ計算しておいた全イベントの \(C_i\) の総和を引く。

計算量

• 時間計算量: \(O(N \log N)\)
  • 時刻のソート（座標圧縮）に \(O(N \log N)\) かかります。
  • DPの遷移は各イベントを1回ずつ確認するため \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 座標圧縮用のマップやDPテーブル、イベントのリストの保存に \(O(N)\) のメモリを使用します。

実装のポイント

• 半開区間の扱い: 問題文にある通り \([L_i, R_i)\) なので、終了時刻 \(R_i\) と別のイベントの開始時刻 \(L_j\) が一致していても重なりとはみなしません。DPの遷移で dp[l_idx] + w とすることで、時刻 \(L_i\) ちょうどに終わる別のイベントの結果をそのまま引き継げるため、正しく処理できます。

• 高速な入出力: \(N\) が \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。

  ソースコード

import sys

def solve():
    # Fast I/O: read all input at once and use an iterator for memory and time efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # Use an iterator to process data efficiently
    data_iter = iter(map(int, input_data))
    
    try:
        N = next(data_iter)
        B = next(data_iter)
    except StopIteration:
        return
    
    events = []
    coords_set = set()
    total_c = 0
    
    # Parse events and collect unique coordinates for compression
    for _ in range(N):
        try:
            l = next(data_iter)
            r = next(data_iter)
            c = next(data_iter)
            # The weight of an event is the profit B plus the avoided cancellation cost C_i
            w = B + c
            events.append((l, r, w))
            coords_set.add(l)
            coords_set.add(r)
            total_c += c
        except StopIteration:
            break
        
    # Coordinate compression: Map large time values to a range [0, M-1]
    # sorted_coords: all unique L_i and R_i in ascending order
    sorted_coords = sorted(coords_set)
    # coord_map: mapping from time to its index in sorted_coords
    coord_map = {val: i for i, val in enumerate(sorted_coords)}
    M = len(sorted_coords)
    
    # Group intervals by their compressed end time index
    adj = [[] for _ in range(M)]
    for l, r, w in events:
        adj[coord_map[r]].append((coord_map[l], w))
        
    # dp[i]: max weight of non-overlapping intervals ending at or before sorted_coords[i]
    dp = [0] * M
    for i in range(M):
        # The current max weight is at least the max weight from the previous coordinate
        if i > 0:
            dp[i] = dp[i-1]
        
        # Check all events ending exactly at the current coordinate sorted_coords[i]
        # Each event can be combined with the best set of events ending at or before its start time.
        # Problem states that if one ends at t and another starts at t, they do not overlap.
        # This is handled because dp[l_idx] represents the max weight of intervals ending at or before sorted_coords[l_idx].
        for l_idx, w in adj[i]:
            new_w = dp[l_idx] + w
            if new_w > dp[i]:
                dp[i] = new_w
                
    # Final maximum profit calculation
    # The objective is to maximize: |S| * B - Sum_{i not in S} C_i
    # This is equivalent to maximizing: Sum_{i in S} (B + C_i) - Sum_{all i} C_i
    # dp[M-1] gives the maximum Sum_{i in S} (B + C_i) for non-overlapping intervals.
    if M > 0:
        print(dp[M-1] - total_c)
    else:
        # If N=0 (though N >= 1 by constraints), profit is 0
        print(0)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。