人権なし

競プロで解いた問題や開発の進捗などの記録です

大手前プロコン 2019:G - 空をかけるピ太郎 (Pitaro, who Leaps through Air)

問題

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g

解法

N が大きいので,P, Q, R, S, A_i, B_i, C_i, D_i を x, y 座標に分けて座標圧縮をする.また,上下・左右方向にワープ可能な領域をそれぞれ累積和で求めておく.このとき,別のワープ可能な領域が隣り合っているとき,隣り合っているところをまたぐ際にコストが生じるので,累積和を求める段階で 0 を検出したらコストがかかると判定する必要がある.これで各マス間の移動のコストが求まったので,二次元平面上でダイクストラ法を使って (P, Q) から (R, S) の最短距離を求めればよい.O(M^2 * logM).

解答

https://atcoder.jp/contests/otemae2019/submissions/6723072

実装がかなり大変だった.

f:id:babcs2035:20190805161237p:plain