# ABC188 D - Snuke Prime
ABC188 D - Snuke Prime
問題へのリンク
問題概要
株式会社すぬけは様々なサービスを提供している。各サービスの利用料は
制約
ABC中の解答
ある日のサービス利用料が TLE
になってしまう(ちなみに自分のパソコンで試してみたらフリーズしそうになったのであわてて強制終了した)。
次に以前連続した区間の問題があって知人と感想戦したなと思い出し問題を確認したら ABC179 D - Leaping Tak を見つけた。解説をしばらく見たけど「うーんこれじゃないなぁ。でもこういうふうに計算量落とすんだろうな」とハマってしまい30分ぐらい消費してしまった。(たまにこういうふうにハマってしまう。競プロの面白いところでもあるのですが)
気分転換に家事をした後、
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 日目の間に料金がa_i 円上がるイベントが起こるc_i -
日目とb_i 日目の間に料金がb_i + 1 円下がるイベントが起こるc_i
こうすることで私のABC中の解答同様イベントが多くて
解答のコードを読まずに文章だけ読んで実装した時に
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中の解答同様座圧をしていもす法をするというものであった。ただ、私の座圧は辞書2つを用いて無理やり処理をしたためあまりきれいではなく、きりさんが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)
Discussion