競技プログラミング用 知識集積所
ABC429F - Shortest Path Query
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
高さが3マスしかないということは、左に移動するのが最短経路になることはない。
つまり、上下右の3つの移動だけで考えればよく、しかも右へ行く回数は絶対にn-1回である。
よって、上下移動の最少回数だけ考えればよい。
つまり、上下右の3つの移動だけで考えればよく、しかも右へ行く回数は絶対にn-1回である。
よって、上下移動の最少回数だけ考えればよい。
各マスの左右辺に、そこを横切るかどうかのチェッカーを置くことを考える。
すると、i列目をある段で抜けてからj列目のある段をある段で抜けるまでの最小上下動回数は、各列での縦移動回数を表現した行列のトロピカル半環※を用いた積で9通り全てを表現することが可能である。
すると、i列目をある段で抜けてからj列目のある段をある段で抜けるまでの最小上下動回数は、各列での縦移動回数を表現した行列のトロピカル半環※を用いた積で9通り全てを表現することが可能である。
この積の中身は更新されるので、segment木※に行列を載せてやればよい。
答えるべき値は、可能なら全体の積の(0,2)成分の値にn-1を足した値、不可能なら-1となる。
答えるべき値は、可能なら全体の積の(0,2)成分の値にn-1を足した値、不可能なら-1となる。
解答例
解答例
TLEが不安な場合、以下で定数倍程度高速化可能。
TLEが不安な場合、以下で定数倍程度高速化可能。
