概要

互いに時間帯が重ならないイベントの集合を選び、受理による収益からキャンセル補償費用を引いた利得を最大化する問題です。式変形により「重み付き区間スケジューリング問題」に帰着できます。

考察

利得の式変形

受理するイベントの集合を \(S\) とすると、利得は次のように表されます。

\[|S| \times B - \sum_{i \notin S} C_i\]

ここで、却下されたイベントの補償費用の合計を変形します。

\[\sum_{i \notin S} C_i = \sum_{i=1}^{N} C_i - \sum_{i \in S} C_i\]

これを利得の式に代入すると、

\[|S| \times B - \left(\sum_{i=1}^{N} C_i - \sum_{i \in S} C_i\right) = \sum_{i \in S}(B + C_i) - \sum_{i=1}^{N} C_i\]

\(\sum_{i=1}^{N} C_i\) は定数なので、利得の最大化は \(\sum_{i \in S}(B + C_i)\) の最大化と等価です。

問題の帰着

各イベント \(i\) に重み \(w_i = B + C_i\) を割り当て、互いに重ならない区間の集合で重みの合計を最大化する問題になります。これは典型的な重み付き区間スケジューリング問題（Weighted Interval Scheduling）です。

素朴なアプローチの問題

全てのイベントの部分集合を列挙すると \(O(2^N)\) で、\(N \leq 2 \times 10^5\) では到底間に合いません。動的計画法と二分探索を組み合わせることで効率的に解けます。

アルゴリズム

1. 前処理: 全イベントを終了時刻 \(R_i\) の昇順にソートする。
2. DP定義: \(dp[i]\) を「ソート後の先頭 \(i\) 個のイベントだけを候補としたとき、選べる重みの合計の最大値」とする。\(dp[0] = 0\)。
3. 遷移: \(i\) 番目のイベント（0-indexed）について、
   • 選ばない場合: \(dp[i+1] = dp[i]\)
   • 選ぶ場合: このイベントと重ならない直前のイベントを探す。具体的には、\(R_j \leq L_i\) を満たす最大の \(j\) を二分探索で求め、\(dp[i+1] = w_i + dp[j\) の個数\(]\) とする。
   • 両者の \(\max\) を取る。
4. 答えの計算: \(dp[N] - \sum_{i=1}^{N} C_i\) を出力する。

具体例

例えば、イベントが \([1, 3), [2, 5), [4, 6)\) で \(B = 10\), \(C = [3, 2, 5]\) の場合： - 重み: \(w = [13, 12, 15]\) - 終了時刻でソート済み（この順） - イベント \([4, 6)\) を選ぶ際、\(R_j \leq 4\) を満たすのはイベント \([1, 3)\) なので、\([1,3)\) と \([4,6)\) を同時に選べ、重みの合計は \(13 + 15 = 28\) - 利得: \(28 - (3+2+5) = 18\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートに \(O(N \log N)\)、各イベントの二分探索に \(O(\log N)\)）
• 空間計算量: \(O(N)\)（DP配列とイベント情報の格納）

実装のポイント

• 半開区間の扱い: 区間 \([L_i, R_i)\) が重ならない条件は \(R_j \leq L_i\) です。bisect_right(ends, L_i, 0, i) で「終了時刻が \(L_i\) 以下」のイベント数を正しく求められます。端点が一致する場合（\(R_j = L_i\)）は重ならないため、bisect_right が適切です。

• 答えが負になる場合: 全て却下しても補償費用がかかるため、答えが負になりうる点に注意。特別な場合分けは不要で、式 \(dp[N] - \text{total\_C}\) がそのまま正しい答えを返します。

• オーバーフロー: Python は多倍長整数なので心配不要ですが、C++ 等で実装する場合は long long が必要です（\(B + C_i\) が最大 \(2 \times 10^9\)、\(N\) が \(2 \times 10^5\) なので合計は最大約 \(4 \times 10^{14}\)）。

  ソースコード

import sys
from bisect import bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    
    events = []
    total_C = 0
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        events.append((L, R, C))
        total_C += C
    
    # Profit = |S| * B - sum_{i not in S} C_i
    #        = |S| * B - (total_C - sum_{i in S} C_i)
    #        = sum_{i in S} (B + C_i) - total_C
    #
    # So we want to maximize sum_{i in S} (B + C_i) where S is a set of 
    # non-overlapping intervals (half-open [L_i, R_i)).
    # This is a weighted interval scheduling problem.
    
    # Weight of each event
    weights = [(events[i][0], events[i][1], B + events[i][2]) for i in range(N)]
    
    # Sort by end time
    weights.sort(key=lambda x: x[1])
    
    ends = [w[1] for w in weights]
    
    # dp[i] = max weight using events from the first i events (0-indexed: events 0..i-1)
    # dp[0] = 0
    # dp[i] = max(dp[i-1], w_i + dp[j]) where j is the largest index such that ends[j] <= L_i
    
    dp = [0] * (N + 1)
    
    for i in range(N):
        L_i, R_i, w_i = weights[i]
        # Find largest j such that ends[j] <= L_i, i.e., j+1 events considered
        # ends is sorted. We want rightmost index where ends[idx] <= L_i
        # bisect_right(ends, L_i) gives the number of elements <= L_i... no.
        # bisect_right(ends, L_i) gives first index where ends[index] > L_i
        # So the number of events (among first i events, indices 0..i-1) with end <= L_i
        # But we only look at ends[0..i-1] since we're considering event i (0-indexed)
        # Actually, ends has all N elements. We want among indices 0..i-1.
        
        j = bisect_right(ends, L_i, 0, i)  # number of events among 0..i-1 with end <= L_i
        
        dp[i + 1] = max(dp[i], w_i + dp[j])
    
    max_weight_sum = dp[N]
    answer = max_weight_sum - total_C
    
    print(answer)

main()

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