ABC177 F - I hate Shortest Path Problem - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

縦 ${H+1}$ 横 ${W}$ マスのマス目の一番上のマスから1つを選んで右か下に1マスずつ移動する. ただし, ${i}$ 行目の ${[A_i, B_i]}$ マスから下に移動することはできない. ${1\leq k\leq H}$ の ${k}$ について, ${k+1}$ 行目のいずれかのマスに移動するための最小移動回数を求めよ.

${1\leq H,W\leq 2×10^5\\ 1\leq A_i < B_i\leq W}$

思考の流れ

グリッド上で右か下に移動するやつと言ったらDPだけど制約がでかいからきつそう. DP書いてみて高速化してもいいけど今回はやめておく.

${\downarrow}$

右か下にしか動かないからあるマスからあるマスの移動回数は2マス間のマンハッタン距離になる. 下への移動回数は ${k}$ 回なので, 1行目のいずれかのマスとそのマスから到達可能な ${k}$ 行目のマスとの横方向の距離の最小値 ${+k}$ が答え.

${\downarrow}$

下に進むことができないようなマスがあるので, そのときは右に進む. また, 下に進むことができるのにわざわざ右に行く必要はないことは容易に想像がつく. よって1行目から順に, 一行目のマスからスタートしたら ${k}$ 行目にはどこにいるかをシミュレーションしていけば ${O(HW)}$ では解ける.

高速化できる点として, 下に行けるマスは「今どこにいるか」という情報の更新が必要なかったり, 下に行けないマスは連続になっているかつすべて同じ位置になっていることを利用したりするものが考えられる.

${\downarrow}$

必要な部分のみ更新したい. 結局こんな問題が解きたい(クエリに答えたい).

更新
- ${k}$ 行目で ${A_k}$ 以上 ${B_k}$ 以下にいるものを ${B_k+1}$ に移動させる. ${B_k+1}$ が範囲外なら ${\infty}$ に移動するものとする.
最小値取得
- ${k}$ 行目で今いるマスとスタート位置のマスの横方向の距離の最小値を求める.

ここで, 更新の際に最小値となり得るのは, 今いるマスが ${A_k}$ 以上 ${B_k+1}$ 以下のもののなかでスタート位置が最も右のものであることはすぐにわかる. さらに, スタート位置が ${i}$ 番目で今いるマスが ${a_i}$ という数列は常に広義単調増加であるので, 結局, 今いるマスが ${A_k}$ 以上 ${B_k+1}$ 以下のもののなかで最も右のものが答えとなる. これはsetで管理すれば解ける. 具体的には,

(今いる位置, スタート位置)をsetで, 今いる位置とスタート位置の距離をmultisetでもち, 今いる位置が ${A_k}$ 以上 ${B_k+1}$ 以下のところの一番右( ${B_k+1}$ に近い)のものだけを残し他は消す. 削除回数は各要素高々1回なのでまにあう. 残した部分の今いる位置とスタート位置の距離を計算すればmultisetで最小値が求められる.

他にも...
遅延セグ木で ${[l,r)}$ を ${1,2,3,...}$ (等差数列)に変更するクエリが ${O(\log N)}$ でできたら以下のプログラムのように簡単に解ける(update_linear_queryが等差数列での更新).

int main() {
    int h,w;cin >> h >> w;
    constexpr int INF = 1e9 + 6;
    LazySegmentTree<ll> seg(w,0);
    for (int i = 0; i < h; i++) {
        int a,b;cin >> a >> b;
        seg.add_query(0,w,1);
        if (a == 1) seg.update_linear_query(a-1,b,0,INF);
        else seg.update_linear_query(a-1,b,1,seg[a-2]-a+2);
        ll ans = seg.get_query(0,w);
        cout << (ans >= INF ? -1 : ans) << endl;
    }
    return 0;
}