ABC128 E - Roadwork
問題原文
問題要旨
数直線と見なすことのできる道路がある。
この道路で 回工事が行われる。工事 は、時刻 [S_i - 0.5] から 時刻 [T_i - 0.5] まで座標 を通行不能にする。
また 人の人がいる。人 は時刻 に座標0から数直線を出発し、時速1で右に進む。工事中の座標にたどり着いたら、そこで止まる。
各人について、進む距離を求めよ。ただし、無限に進み続けられる場合は -1とせよ。
- のとき、 と は重ならない
解法
まず、ある工事 に引っかかるような人は、 時刻 に出発した人と言い換えて良い。
また今回のような、有効期限付き条件 を取り扱うのには、イベントソートが有効。
イメージは、「今通行止めの座標を管理するもの」に「座標追加イベント」と「座標削除イベント」で操作をしていく。
あるタイミングからスイッチを入れておいて、あるタイミングでスイッチを切るイメージ。「イベントをどこまで見たか?」を管理するマーカーもあるとよい。
各人の判定においては、今通行止めされている座標のうち最小のもの(なければ−1)とすればよい。
実装
あまりにも罠が多く、高速化があまりにも地獄。
まず、 今通行止めの座標の中から最小値を取り出すのに、min(set)を使うことはできない。
min(set) は 実は O(N)
で間に合わない。。。
また、各人のチェックについてもイベント化する方が早くなる。
またイベントの持ち方はタプルを使う。
if _name_ == '__main__'
も使う。
sys.stdin.readline()
も忘れずに使う。
最小値の計算には heapq
を使う。
現在の最小値候補が、現在通行止めの座標の中に入っているまで、heapq
から取り出し続ける。
イベントの優先順位にも注意する。
優先度は、 削除 → 追加 → 判定 の順。
判定が最後なのはそれはそうとして、削除が追加より先なのが不思議に思えるが、ある1つの工事については 削除イベントが追加イベントより先に来ることはないので大丈夫。むしろ追加→削除 だと ある2つの工事で同じ座標を 追加、追加、削除、削除、とするときに、途中で set
がこわれる。
defalultdict
を使えば回避できるが、使わない方が早いはず。
あと PyPyじゃなくてPythonでないと通らない。set
とかheapq
が遅いんだろうか。。。わからない
def main(): import sys import heapq N, Q = map(int, sys.stdin.readline().split()) events = [] for i in range(N): s, t, x = map(int, sys.stdin.readline().split()) events.append((s - x, 1, x)) # 通行止め追加 events.append((t - x, -1, x)) # 通行止め削除 for i in range(Q): d = int(input()) events.append((d, 2, 0)) # チェックイベント events.sort() events.append([float('inf'), 'guard', None]) i = 0 closing = set() hq = [] # 最小値を高速に入手するため while d >= events[i][0]: time, event, x = events[i] if event == 1: closing.add(x) heapq.heappush(hq, x) elif event == -1: closing.remove(x) else: while hq and (hq[0] not in closing): heapq.heappop(hq) if hq: print(hq[0]) else: print(-1) i += 1 if __name__ == '__main__': main()
感想
解法の核は、
と似ている。
でも実装が地獄。ほんとに地獄。
Pythonの min(set) は O(N)
だということを、心に刻んでおく。。。
あと細かい高速化テクニックも。