全国統一プログラミング王決定戦本戦-F Flights

問題概要

N個の頂点があり、各頂点はx,y座標とコストを持っている。これらをx,y,costで表す。頂点i,jを考えたときに、 $x_i \leqq x_j , y_i \leqq y_j$ を満たすときにij間に距離 $cost_j$ の辺が貼られる。

スタートからゴールまでの距離の最小値を求めたい。距離は $dist$ で表す。

メモ

まずスタートとゴールを $(x,y)$ で比較したときに、常にスタートが小さくなるようスタートをゴールを入れ替えても一般性を失わない。

$(x,y)$ の昇順に頂点を見ていくことで、移動を「左下からの移動」「左下への移動」の2種類のみとして考えることができる。

左下からの移動

頂点iに左下にある頂点kから移動する場合

$dist_i=min(dist_k)+cost_i$ である。

これは各頂点に対して $O(N)$ であるため後に高速化することを考える。

左下への移動

頂点iから左下にある頂点kへ移動する場合、全てのkに対して

$dist_k=min(dist_k,dist_i+cost_i)$ である。

これも各頂点に対して $O(N)$ であるため後に高速化することを考える。

またこの時ゴールの右上にあるすべての頂点kも考えて、

$ans=min(dist_i,min(dist_k+cost_k))$ である。

mapを用いた高速化

$(y,x)$ をキーにして $dist$ を持つmapを用いることで、2種類の移動の際に見るべき頂点の数を1つにすることができる。これを実現するためにはmapの値が常に単調減少であるようにすれば良い。

頂点iを見ているときのことを考える。

左下からの移動

mapの値が単調減少であれば、 $(y_i,x_i)$ よりも小さい要素をキーに持つ要素の中でキーが一番大きな要素のみを見たら良い。これはlower_boundとprevを用いることなどで値の更新ができる。もしそのような要素が無ければその頂点にたどり着くことは不可能である。

但し追加の過程で単調減少でなくなる場合があるので、その場合mapから頂点iを削除するか、頂点iよりも後の要素の値が頂点iでの値よりも小さくなるまで頂点iの直後の要素を削除し続けることで単調減少を維持することができる。

左下への移動

mapの先頭から見ていって値が $dist_i+cost_i$ よりも大きい要素を $dist_i+cost_i$ に変更することで値の更新ができる。ここでも単調減少でなる場合があるので、mapの先頭の値よりも2番目の値が小さくなるまで2番目の要素を削除し続けることで単調減少を維持することができる。