概要
問題文 → ■
自分の提出 → ■
公式解説 → ？（ありますか？）
問題名で検索すると、他の方の解説をたくさん書いてくださっています。
共通として二分探索による解法が多くとりあげられていました。私は二分探索を使っておらず、別解っぽいやつだったので、記しておきます。計算量も、dijkstra法 1回 なので、安くなっています。
解法
この問題の本質的に難しいポイントとして、
・出発点からあるセル $v$ までの経路を全て列挙できたとしても、そのうちどれが最適であるのかが分からない。
ということが挙げられます。$v$ からゴールまで進む過程でどうせとても暗い道を通るならば、$v$ までは道中の明るさを気にせずに最短経路で行くべきです。一方、$v$ からゴールへ明るいセルだけを通り辿り着けるならば、$v$ までに暗い道を通っていると、そこがボトルネックになってしまいます。
これを克服する 1 つの方法が、「目標スコアを決め打って二分探索」というもので、この場合には、$v$ までの経路のうちの最適解は「指定された明るさをキープした上での最短時間を達成する経路」であると分かります。このように各時点での最適解を1つだけ覚えていけばよいので、 二分探索とdijkstra法を合わせることで計算できます。
別路線で行きます。最適な経路の特性として、
・あるセル $v$ からゴールまでの経路を全て列挙できれば、そのうちどれが最適であるのかが分かる
という性質が挙げられます。セル $v$ までで実現した明るさの最小値や、そこまでにかかった時間に依りません。したがって、各頂点に対して「その頂点を時刻 $0$ に出発したとしたときの、経路の明るさの最小値」を持たせるようにして、ゴールから始めてdijkstra法を行えばよいです。
コメント
- 割と自然な問題の見方だったと思うけど、少数派だったようです。ソースコードはかなり昔のものなので、粗が多いかもしれません。
