🐍

# ABC188 D - Snuke Prime

2021/01/13に公開

いもす法

座圧

abc188

区間データ

tech

ABC188 D - Snuke Prime

問題へのリンク

問題概要

株式会社すぬけは様々なサービスを提供している。各サービスの利用料は $c_i$ であり今日を１日目として、 $a_i$ 日目の始めから $b_i$ 日目の終わりまで利用する予定である。すぬけプライムというサービスに加入していると１日あたり $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 \times 2 \times 10^5$ と思い、座標圧縮(座圧)をしサービス利用金額を求め、座圧前の点の間の距離とサービス利用金額がかけて足すことで合計金額を求めた。少し時間をかけすぎてしまったがAC

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

# a, b, c   i番目のサービスはa日のはじめからb日の終わりまでつかう。１日あたり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

区間ではなく始まりと終わりの２点だけに注目し以下のようなイベントとみなす(ちなみに私は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 \times 2 \times 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)

公式解法2

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

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)