概要

重ならないようにイベントをいくつか受理するとき、利得を最大にする問題です。式変形により「各イベントに重みを付けた区間スケジューリング（重み付き区間選択）」に帰着し、DPで解きます。

考察

1) 利得の式を「受理したイベントの得点最大化」に言い換える

利得は $\(|S|\times B - \sum_{i\notin S} C_i\)\( です。ここで \)\sum_{i\notin S} Ci\( は「全体の \)C\( の合計」から「受理した分の \)C$ の合計」を引いたものなので、 [ |S|B - \left(\sum{i=1}^N Ci - \sum{i\in S} Ci\right) = -\sum{i=1}^N Ci + \sum{i\in S}(B + C_i) ] となります。

つまり、 - \(-\sum C_i\) はどの選び方でも一定（定数） - 最大化すべきは \(\sum_{i\in S}(B+C_i)\)

と分かります。よって「イベント \(i\) を選ぶと重み \(W_i=B+C_i\) を得る」とみなして、重ならない区間集合の重み最大化を解けばよいです。

2) 素朴解が無理な理由

重なり判定をしながら全探索すると \(2^N\) 通りで不可能です。
また、DPをしても「直前にどのイベントを選んだか」で状態が爆発しがちですが、区間問題は終了時刻でソートすると「直前に両立する最後のイベント」を二分探索で求められ、1次元DPで済みます。

3) 半開区間の扱い

区間は \([L_i, R_i)\) なので、端点が接する（\(R_j = L_i\)）場合は重なりません。
したがって「両立条件」は $\(R_j \le L_i\)$ です。これを二分探索で扱えるようにします。

アルゴリズム

1. 全イベントについて \(C\) の総和 \(\text{sumC}=\sum C_i\) を計算する。
2. 各イベントを
   • 終了時刻 \(R\)
   • 開始時刻 \(L\)
   • 重み \(W = B + C\) のタプル \((R, L, W)\) として持ち、\(R\) 昇順にソートする。
3. DPを定義する：
   • \(dp[i]\) = 「ソート後の先頭から \(i\) 個（1..i）までを見たときの、得られる重みの最大値」
4. 遷移：
   • \(i\) 番目のイベント（配列では \(i-1\)）を選ばない：\(dp[i-1]\)
   • 選ぶ：両立する直前までの最適 \(dp[p] + W\)

ここで \(p\) は「終了時刻が \(L\) 以下のイベントの個数」なので、終了時刻配列 ends に対して $\(p = \text{bisect\_right}(ends, L)\)$ で求まります（ends[p-1] <= L を満たす最大の位置までが両立）。

よって [ dp[i] = \max(dp[i-1],\ dp[p] + W) ] 5. 最終的な答えは、元の利得に戻して [ \text{ans} = -\text{sumC} + dp[N] ] を出力する。

計算量

• 時間計算量: \(O(N\log N)\)（ソート \(O(N\log N)\) + 各DPで二分探索 \(O(\log N)\) を \(N\) 回）
• 空間計算量: \(O(N)\)（イベント配列、ends、dp など）

実装のポイント

• 重なり判定が半開区間 \([L,R)\) なので、両立条件は \(R \le L\)。二分探索は bisect_right(ends, L) が適切です。

• DP配列は dp[0]=0 とし、dp[i] を「先頭から i 個まで」とすることで、dp[p] をそのまま参照できます。

• 答えは負になる可能性があるので、最後に -sumC + dp[N] をそのまま出力します。

  ソースコード

import sys
import bisect

def main():
    input = sys.stdin.buffer.readline
    N, B = map(int, input().split())
    events = []
    sumC = 0
    for _ in range(N):
        L, R, C = map(int, input().split())
        sumC += C
        events.append((R, L, B + C))

    events.sort()  # sort by end time R

    ends = [0] * N
    Ls = [0] * N
    Ws = [0] * N
    for i, (R, L, W) in enumerate(events):
        ends[i] = R
        Ls[i] = L
        Ws[i] = W

    dp = [0] * (N + 1)
    for i in range(1, N + 1):
        L = Ls[i - 1]
        W = Ws[i - 1]
        p = bisect.bisect_right(ends, L)  # number of intervals with end <= L
        cand = dp[p] + W
        dp[i] = dp[i - 1] if dp[i - 1] >= cand else cand

    ans = -sumC + dp[N]
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。