SamCoding Round 10 (Div. 4) C - Chakra Run
忍者が数直線上を地点 から地点 まで走ります。 メートル走るごとにチャクラを 消費し、最初はチャクラを 持っています。道の途中に 軒のラーメン屋があり、 軒目は地点 にあって、立ち寄るとチャクラが 増えます(チャクラに上限はありません)。到着した時点でチャクラがちょうど でも立ち寄れます。地点 に着くまでに立ち寄る回数の最小値を求め、たどり着けないなら を出力する問題です(、)。
立ち寄った店の集合を決めると、走れる距離は にその店の の和を足したものです。どの店に立ち寄るかの順番は関係なく、「地点 にたどり着けるか」は、 より手前で立ち寄った店だけで決まります。
そこで、前から順に店を見ていき、通り過ぎた店をいったん「候補」としてためておきます。次の店(または地点 )までたどり着けないときは、それまでの候補の中から が最大の店に「さかのぼって立ち寄ったことにする」のを、たどり着けるようになるまで繰り返します。候補が尽きたらたどり着けないので です。
各時点で、立ち寄る回数を増やすなら、手前の店の中で が最大のものを選ぶのが最も遠くまで走れます。なので、この貪欲法で立ち寄る回数が最小になります。候補から最大値を取り出すのは優先度付きキュー(ヒープ)でできるので、計算量は です。
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 = 0for 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 は「今たどり着ける最も遠い地点」として使っています。末尾に地点 を の店として足し、ゴールも店と同じように判定しています。heapq は最小値を取り出すヒープなので、 を入れて最大値を取り出しています。