AtCoder-ABC188 D - Snuke Prime【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

AtCoder Beginner Contest188では解けなかったD問題を再度取り組みました。
公式解説から学習した内容と、提出したNG例を記載します。
AtCoder Beginner Contest 188 - AtCoder

AtCoder Beginner Contest188 D - Snuke Prime

問題文

株式会社すぬけは様々なサービスを提供しています。
この会社は、すぬけプライムという支払いプランを用意しています。
すぬけプライムへの加入中は、1 日あたり C 円を支払うことで、提供される全てのサービスを追加料金の支払いなしに利用することができます。
すぬけプライムへの加入および脱退は、それぞれ 1 日の始めおよび終わりに自由に行うことができます。
高橋くんは、この会社のサービスのうち N 個を利用しようとしています。
そのうち i 個目のサービスは、今日を 1 日目として、ai 日目の始めから bi 日目の終わりまで利用する予定です。
すぬけプライムに加入していない期間中は、i 個目のサービスを利用する際に 1 日あたり ci 円を支払う必要があります。
サービスを利用するために高橋くんが支払う必要のある最小の合計金額を求めてください。

制約

・1≤N≤2× $10^5$ ・1≤C≤ $10^9$
・1≤ai≤bi≤ $10^9$
・1≤ci≤ $10^9$
・入力に含まれる値は全て整数

解答例

N, C = map(int,input().split())

event = []
for i in range(N):
    a, b, c = map(int,input().split())
    a -= 1
    event.append((a, c))
    event.append((b, -c))

event.sort()

ans = 0
price = 0
time = 0

for x, y in event:
    if x != time:
        ans += min(C, price) * (x- time)
        time = x
    price += y

print(ans)

解説

ある期間中だけ加入するサービスがN個あり、i番目のサービス加入中はciだけ費用がかかります。
すぬけプライムに加入すると費用Cですべてのサービスが使用できます。
最小でいくらの費用で利用できるか求める問題です。

公式解説の通りに二次元配列eventを作成し各サービス加入日ai-1と費用ci、およびサービスをやめるbiと-ciを格納していきます。
そのあと、二次元配列eventをソートします。
二次元配列のソートは初めてだったので学習し、こちらの記事にまとめました。
ebisuke33.hatenablog.com

その後はイベントが起こるタイミングで合計費用を足していきました。
各サービスの合計費用がすぬけプライムの加入費用Cを超えたら、金額はCとします。
いもす法を以前学習したので理解しやすかったです。
いもす法を用いた問題も過去に記事にしましたので参考までにのせておきます。
ebisuke33.hatenablog.com

ループを抜けてans変数を出力してACでした。

NG例

n, c = map(int,input().split())

A = []
B = []
C = []
for i in range(n):
    a, b, cc = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(cc)

day = [0 for i in range(max(B) + 5)]
for i in range(n):
    day[A[i]] += C[i]
    day[B[i] + 1] -= C[i]

ans = 0
for i in range(max(B) + 1):
    day[i+1] += day[i]
    if day[i+1] >= c:
        ans += c
    else:
        ans += day[i+1]

print(ans)