Wedding Juicer

先日の練習会で出たPKU2272 Wedding Juicerについて。ネタバレ含。

あるマスxに着目する。xから出発して外周マスまで行くような道の全体を考えると、xの最高水位は、{ {道上のマスの高さの最高値} の全ての道に対する最小値 } に等しい。

そこで、各マスを点とし、隣り合っているマスに枝を張り、加えて全ての外周マスとつながっている点sを追加したグラフを考え、有向枝の重みを、枝の行き先の点に対応するマスの高さとする。するとマスxの水位を求める問題はこのグラフ上では、{ {sから出発してxにたどり着くような道の、枝の重みの最大値} の最小値} を求める問題になる。これはダイクストラ的なアルゴリズムで解くことができる。

... ということを思いついて、言葉で説明しようと思ったのだけど、どうも上手くできない。説明できないってことは分かってないってことなんだよなぁ…