# ABC188 D - Snuke Prime

3 min read読了の目安(約3400字

ABC188 D - Snuke Prime

問題へのリンク

https://atcoder.jp/contests/abc188/tasks/abc188_d

問題概要

株式会社すぬけは様々なサービスを提供している。各サービスの利用料は c_i であり今日を1日目として、 a_i 日目の始めから b_i 日目の終わりまで利用する予定である。すぬけプライムというサービスに加入していると1日あたり C 円払うことですべてのサービスを追加料金の支払いなしに利用できる。サービスを利用するために支払う必要のある最小の合計金額を求める。

制約

1 \leqq N \leqq 2 × 10^5
1 \leqq C \leqq 10^9
1 \leqq a_i \leqq b_i \leqq 10^9
1 \leqq c_i \leqq 10^9

ABC中の解答

ある日のサービス利用料が C を超えているかを計算する問題。いもす法を使えばいいかな?と思ったけど b_i の最大値が 10^9 のため、この大きさの配列を用意し for ループを回すのは TLE になってしまう(ちなみに自分のパソコンで試してみたらフリーズしそうになったのであわてて強制終了した)。
次に以前連続した区間の問題があって知人と感想戦したなと思い出し問題を確認したら ABC179 D - Leaping Tak を見つけた。解説をしばらく見たけど「うーんこれじゃないなぁ。でもこういうふうに計算量落とすんだろうな」とハマってしまい30分ぐらい消費してしまった。(たまにこういうふうにハマってしまう。競プロの面白いところでもあるのですが)
気分転換に家事をした後、 1 \leqq N \leqq 2 × 10^5 なので実際にサービス利用金額が変化するのは多くて 2 × 2 × 10^5 と思い、座標圧縮(座圧)をしサービス利用金額を求め、座圧前の点の間の距離とサービス利用金額がかけて足すことで合計金額を求めた。少し時間をかけすぎてしまったがAC

N, C = map(int, input().split())  # N個のサービス, すぬけプライムの値段C円

# a, b, c   i番目のサービスはa日のはじめからb日の終わりまでつかう。1日あたりc円かかる
# いもす法?10**9は配列にすると多すぎるから各サービスのa,bのみに圧縮する?それなら多くても2*10**5 * 2個でOK

ABC = []
dates = set([])
for _ in range(N):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    dates.add(a)
    dates.add(b)
    dates.add(b + 1)
dates = sorted(dates)

dic1 = {}
dic2 = {}
for i, date in enumerate(dates):
    dic1[i] = date
    dic2[date] = i

V = [0] * len(dates)
for a, b, c in ABC:
    V[dic2[a]] += c
    V[dic2[b + 1]] += -c
for i in range(1, len(V)):
    V[i] = V[i] + V[i - 1]

ans = 0
for i in range(len(V) - 1):
    diff = dic1[i + 1] - dic1[i]
    ans += min(V[i] * diff, C * diff)
print(ans)

公式解法1

区間ではなく始まりと終わりの2点だけに注目し以下のようなイベントとみなす(ちなみに私はABC中の解答では a_i - 1, b_i 日目の代わりに a_i, b_i + 1 日目として処理していた)

  • a_i - 1 日目と a_i 日目の間に料金が c_i 円上がるイベントが起こる
  • b_i 日目と b_i + 1 日目の間に料金が c_i 円下がるイベントが起こる

こうすることで私のABC中の解答同様イベントが多くて 2 × 2 × 10^5 となり O(NlogN) で解くことができる。

解答のコードを読まずに文章だけ読んで実装した時に a, b が同じ値のイベントをどうやってまとめればよいのかわからず、コードを見たらイベント開始時刻(下のコードで x)の値が異なるまでは fee に加算するという処理がされててなるほどと感心した(そしてそのためにイベントをソートをしている)。こういう処理は苦手なので覚えておきたい。

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

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

ans = 0
fee = 0
t = 0
for x, y in events:
    if x != t:
        ans += min(C, fee) * (x - t)
        t = x
    fee += y
print(ans)

https://atcoder.jp/contests/abc188/submissions/19416296

公式解法2

公式解法2は私のABC中の解答同様座圧をしていもす法をするというものであった。ただ、私の座圧は辞書2つを用いて無理やり処理をしたためあまりきれいではなく、きりさんがTwitterで紹介していた座圧がすごいわかりやすかったのでそちらを参考にもう一度実装してみた。
今後はこちらを使わせてもらう。

https://twitter.com/kiri8128/status/1348320381971546117?s=19
N, C = map(int, input().split())

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

sorted_events = sorted(set(events))
D = {e: i for i, e in enumerate(sorted_events)}
compressed_events = [D[e] for e in sorted_events]

V = [0] * len(compressed_events)
for a, b, c in services:
    V[D[a]] += c
    V[D[b]] -= c

for i in range(1, len(V)):
    V[i] = V[i] + V[i - 1]

ans = 0
for i in range(len(V) - 1):
    diff = sorted_events[i + 1] - sorted_events[i]
    ans += min(C, V[i]) * diff
print(ans)

https://atcoder.jp/contests/abc188/submissions/19416697