グラフの単一始点最短経路問題を解くアルゴリズムとして、ベルマンフォード法が知られている。ダイクストラ法と比較すると、計算量を犠牲にして、コストが負の辺にも対応させたというような格好になっている。コストが負の辺は、単にコストが負というだけな…

問題ページ 解法 人々は整数時刻に座標を出発し、速度で正の方向に歩き続けます。よって、時刻から時刻まで座標を通行止めにするということは、時刻に出発した人は座標で通行止めに当たるということになります。人々が歩いている途中に通行止めに当たった場…

問題ページ 解法 ある列の格子点全てにバス停を置くと、任意のその列を跨いだ左右間の移動が可能となり、かつ総移動距離がマンハッタン距離と等しくなるようにできる。よって、左右独立に考えることができるようになるため、分割統治でこの問題を解くことが…