ABC128 E - Roadwork - かんプリンの学習記録

問題概要
思考の流れ(自分の解法)
思考の流れ(公式解説動画の解法)
思考の流れ(公式解説pdfの解法)
提出プログラム
感想

問題概要

東西に無限に続く1本の大通りがあり, 数直線とみなすことができる. ${1\le N\le 2×10^5}$ 回道路工事が行われる. ${i}$ 番目の道路工事は時刻 ${S_i-0.5}$ から時刻 ${T_i-0.5}$ まで座標 ${X_i}$ を通行止めにする. ${1\le Q\le 2×10^5}$ 人の人が座標0に立っている. ${i}$ 番目の人は時刻 ${D_i}$ に座標0を出発し, 速度1で正の方向へ歩き続ける. 歩いている途中で通行止めとなっている地点に到達した場合には, そこで歩くのをやめる. ${Q}$ 人がそれぞれが進む距離を求めよ.

思考の流れ(自分の解法)

時刻 ${D}$ に座標0を出発した人が時刻 ${S-0.5}$ から ${T-0.5}$ の間に座標 ${X}$ に到達する条件は, ${S-X\le D\le T-1-X}$
各道路工事に対して ${S-X}$ と ${T-1-X}$ を求めておくことで, 各人に対して条件を満たす道路工事のなかでXが最小のものを答えればよい. しかしこのままでは計算量は ${O(NQ)}$ となる.

${\downarrow}$

ここで, ${i}$ 番目の要素が「時刻 ${i}$ に座標0を出発した人が止まる座標」とする配列を作る. 作り方は, 配列の各要素を ${-1}$ に初期化しておき, 各道路工事に対して ${S-X}$ から ${T-1-X}$ 番目の要素に ${X}$ を書いていけばよい. 範囲が重なる場合は ${X}$ が小さい方を書く必要があるので ${X}$ が大きい順に更新していけばいい.
しかし, これだと配列の要素が最大で ${10^9}$ 必要になるし, 更新にも時間がかかる.

${\downarrow}$

これは, 使う座標のみを残した座標圧縮を行えばよい. 使う座標は ${S-X, D, T-1-X}$ である. 更新は遅延評価ができるSegmentTreeなどを用いて更新していけばよい.

思考の流れ(公式解説動画の解法)

解説動画

setに人の出発時刻を入れて, ${X}$ の小さい方から処理していく. ${S-X}$ 以上のものをset上で二分探索して ${T-1-X}$ 以下のものをsetから除いていく. ${X}$ の小さい方から処理しているので, 取り除いかれた時の ${X}$ の値がその人の止まる位置となる. 二分探索や挿入, 削除に ${O(\log{N})}$ かかる. 取り除かれなかったものは, 取り除かれる範囲に無いということなので ${-1}$

思考の流れ(公式解説pdfの解法)

解説pdf

イベントソートというらしい. 今度はsetに工事の情報を入れる. setには常に現在行われている工事( ${S-X}$ から ${T-1-X}$ と考える)の座標が入っているようにする. 現在の時刻を進めていき, 工事の開始時刻にsetに ${X}$ を入れ, 工事の終了時刻に ${X}$ を取り除く. これの実現方法は, まず ${(S-X,1,X)}$ と ${(T-X,-1,X)}$ を各工事ごとに配列に入れソートする. そして, 人の座標0の出発時刻に出発時刻以前の動作(setへの追加,削除)を行う. ${(t,1,X)}$ ならば, ${X}$ をsetに追加し, ${(t,-1,X)}$ ならば ${X}$ をsetから削除する. 各人について動作を行った後の止まる位置はsetにある最小値となる. setに何もない場合は ${-1}$ .