ABC020 C 壁抜け

C

https://beta.atcoder.jp/contests/abc020/submissions/2411640

問題概要

H行W列(H,W<=10)のグリッドが与えられ、それぞれのマスは白か黒であり、白マスのうち2つがスタートとゴールとして与えられる。
白マスを通過するコストが1、黒マスを通過するコストがxの時、コストT以内でゴールに到達できる最大のxを求めよ。

取った方針

エッジにコストがあるときの最短経路はダイクストラで求められる。あとはできるかどうかで二分探索をする。「条件を満たす最大のxを求める」系の問題で、かつできる/できないの境界が定まる(≒コストx以下なら全部できる、xより大きいなら全部できない)場合二分探索が有効。

見た瞬間思いついたが、ダイクストラをバグらせて2時間かかった(実装力～)

正しい方針

同上(ダイクストラ+二分探索)

得られた知見

・「条件を満たす最大のxを求める」系の問題では二分探索が使えることがある。
・グリッド上のダイクストラ
・ダイクストラ法において、既知の最小コストを更新できない場合そのマスはキューに追加しないが、既知のコストがキューに追加するコストと同じ場合でも、キューに追加しない、という箇所を間違っておりバグらせたので覚えておく
66行目(<=であることが重要)(紙ぺーぱーさんありがとうございます)

if (costMap[n.y][n.x] <= n.priority) continue;

・境界はバグりがちなので気を付ける、またバグったら疑う
・バグっていることに気づけない場合は……？

解くのに必要な要素

・グリッドにおけるダイクストラ法
・二分探索

周辺調査によって得られた知見

二分探索にも様々な書き方がある
出典:http://mmxsrup.hatenablog.com/entry/2016/09/20/015201