[AtCoder] C – 暗闇帰り道(ARC 003)

スポンサーリンク

概要

問題文 →
自分の提出 →
公式解説 → ?(ありますか?)

問題名で検索すると、他の方の解説をたくさん書いてくださっています。

共通として二分探索による解法が多くとりあげられていました。私は二分探索を使っておらず、別解っぽいやつだったので、記しておきます。計算量も、dijkstra法 1回 なので、安くなっています。

解法

この問題の本質的に難しいポイントとして、

・出発点からあるセル $v$ までの経路を全て列挙できたとしても、そのうちどれが最適であるのかが分からない。

ということが挙げられます。$v$ からゴールまで進む過程でどうせとても暗い道を通るならば、$v$ までは道中の明るさを気にせずに最短経路で行くべきです。一方、$v$ からゴールへ明るいセルだけを通り辿り着けるならば、$v$ までに暗い道を通っていると、そこがボトルネックになってしまいます。

これを克服する 1 つの方法が、「目標スコアを決め打って二分探索」というもので、この場合には、$v$ までの経路のうちの最適解は「指定された明るさをキープした上での最短時間を達成する経路」であると分かります。このように各時点での最適解を1つだけ覚えていけばよいので、 二分探索とdijkstra法を合わせることで計算できます。

別路線で行きます。最適な経路の特性として、

・あるセル $v$ からゴールまでの経路を全て列挙できれば、そのうちどれが最適であるのかが分かる

という性質が挙げられます。セル $v$ までで実現した明るさの最小値や、そこまでにかかった時間に依りません。したがって、各頂点に対して「その頂点を時刻 $0$ に出発したとしたときの、経路の明るさの最小値」を持たせるようにして、ゴールから始めてdijkstra法を行えばよいです。

コメント

  • 割と自然な問題の見方だったと思うけど、少数派だったようです。ソースコードはかなり昔のものなので、粗が多いかもしれません。

タイトルとURLをコピーしました