ABC237E Skiing
コンテスト中にACしたものの、after_contestでTLEで、嘘解法でした。 この記事は公式解説を自分用にまとめたもので、新たな情報などは無いです。
ここでは、標高が低いところから高いところに行く坂を下り坂、逆を上り坂と言うことにします。
2個目の条件を、
X→Yが登り坂なら楽しさが増加する
と読み替えておきます。
例として、広場1から5へ移動した時の楽しさを考えます。下り坂なら
上り坂なら、
とします。
ここから、広場1から5への楽しさはすべて、
という形式をとり、
は経路によらず一定
という上り坂を取るたびに、
に
が足される
ことがわかります。
よって、を最大化したい時、
を最小化すればよいことになります。
そのため、
- 下り坂なら、
が足される
- 上り坂なら、広場XからYに移動する場合、
というようなグラフを考え、広場1から5までの最短経路を求めればよいことになります。
この時の最小コストをとすれば、
の最大値
は、
として求められます。
上記議論は広場5のみならず、一般の広場でも適用できることが予想できます。そのため、先程の言い換えたグラフにおいて、広場1から、各広場への最短経路
を求めると、その広場での楽しさの最大値
は、
という風に求められ、答えとなる全体での最大値はこれらのmaxを取れば良いと言うことになります。
なお、このグラフのコストは全て非負なのでダイクストラ法が適用でき、で最短経路を求められます。
ポテンシャル
テキストの公式解説ではポテンシャルで説明されていました。
各頂点にポテンシャルを定め、uからvへの有向辺のコスト
を
に変換します。
例えば、
から
への変換後における経路が、
であった時、から
へのコストの和
は、
です。変換前のコストの和は、
なので、
つまり、
は経路によらず一定なので、
を最小化すれば
も最小化されます。よって、変換後の最短経路問題を解けば良いということになります。
これの何が良いかと言えば、負辺を含むグラフについて、ポテンシャルを適切に定めることで、負辺を消してダイクストラ法を適用可能にできるということです。
蟻本によれば、フロー問題で複数回最短経路を求めたいときに最初1回だけベルマンフォード法で最短路を求め、最短路をポテンシャルに設定すると、負辺が消え、以降はダイクストラ法を適用できるようになって計算量が落とせるということでした。
AtCoderの問題でポテンシャルを使用することは無いような気もしますが、今回のように
- 各頂点に何らかの値が設定されている
- 負辺がある
場合にこのような考え方ができないか検討してみるのも良いかと思いました。
