問題リンク
問題概要
\(H+1 \times W \)マスのグリッドがある。
グリッド上は右か下に移動できる。
ただし、上からk行目からk+1行目に移動する時、左から\(A_k\)マス目から\(B_k\)マス目の区間で下方向に移動するのは禁止されている。
一番上のWマスのうちのいずれかからスタートして、k+1行目に到達するまでの最小移動回数を\(1 \leq k \leq H\)に対して求めよ。到達不可能ならば-1を出力せよ。
解法
縦移動の回数は決まっているので、横方向の最小移動回数を求める。
各行のWマスに対し、「その地点に到達するのに必要な横移動の最小回数」を上から順に更新していくことを考える。
区間最小値を求めるsegtreeを使う。
segtreeの中の要素を\(s[i]\)で表す。
k-1行目まで処理したとする。
この時、\(A_k \leq i \leq B_k\)に対し、\(s[i]\)を\(s[A_k - 1]+(i-(A_k - 1))\)で更新すれば良い。(禁止されていないギリギリの区間から回り込むイメージ。\(A_k=1\)の時は別途処理)
これを素直にやると更新が\(O(HW)\)回発生するので高速化する。
sは「1ずつ増加する」いくつかの区間に分割でき、1回の更新で1個の区間で上書きされる。
このような「中身が単純な区間で上書きする」タイプの更新は、区間の端点だけをsetで管理するのが有効(今回は始点だけで良い)。
\(A_k - 1\)と\(B_k+1\)での値を保存しておけば、残りは最小値となり得ないので、setから削除し\(s[i]\) をinfで更新してしまえば良い。
端点の追加・削除の合計回数は\(O(H+W)\)になり、segtreeやsetの操作でlogがつくが十分間に合う。
初期値では、1,...,Wの全てが区間の始点としてsetに全て入れておくと実装が楽になる。
提出
https://atcoder.jp/contests/abc177/submissions/16363990
感想
持ってないデータ構造(なんとかセグ木とか)を使いそうな気がしてめちゃくちゃ焦った。
