コンテンツにスキップ

SamCoding Round 10 (Div. 4) C - Chakra Run

サイト
SamCoding
コンテスト
SamCoding Round 10 (Div. 4)
問題
C - Chakra Run(常設版)

忍者が数直線上を地点 00 から地点 LL まで走ります。11 メートル走るごとにチャクラを 11 消費し、最初はチャクラを cc 持っています。道の途中に nn 軒のラーメン屋があり、ii 軒目は地点 pip_i にあって、立ち寄るとチャクラが aia_i 増えます(チャクラに上限はありません)。到着した時点でチャクラがちょうど 00 でも立ち寄れます。地点 LL に着くまでに立ち寄る回数の最小値を求め、たどり着けないなら −1-1 を出力する問題です(n≤2×105n \le 2 \times 10^5、L,c,ai≤109L, c, a_i \le 10^9)。

立ち寄った店の集合を決めると、走れる距離は cc にその店の aia_i の和を足したものです。どの店に立ち寄るかの順番は関係なく、「地点 xx にたどり着けるか」は、xx より手前で立ち寄った店だけで決まります。

そこで、前から順に店を見ていき、通り過ぎた店をいったん「候補」としてためておきます。次の店(または地点 LL)までたどり着けないときは、それまでの候補の中から aia_i が最大の店に「さかのぼって立ち寄ったことにする」のを、たどり着けるようになるまで繰り返します。候補が尽きたらたどり着けないので −1-1 です。

各時点で、立ち寄る回数を増やすなら、手前の店の中で aia_i が最大のものを選ぶのが最も遠くまで走れます。なので、この貪欲法で立ち寄る回数が最小になります。候補から最大値を取り出すのは優先度付きキュー(ヒープ)でできるので、計算量は O(nlog⁡n)O(n \log n) です。

Python
import heapq
N, L, C = map(int, input().split())
PA = [tuple(map(int, input().split())) for i in range(N)]
PA.append((L, 0))
hq = []
ans = 0
for p, a in PA:
while p > C:
if not hq:
break
C -= heapq.heappop(hq)
ans += 1
if p > C:
print(-1)
break
heapq.heappush(hq, -a)
else:
print(ans)

C は「今たどり着ける最も遠い地点」として使っています。末尾に地点 LL を a=0a = 0 の店として足し、ゴールも店と同じように判定しています。heapq は最小値を取り出すヒープなので、−ai-a_i を入れて最大値を取り出しています。