ABC137-E:Coins Respawn ~負閉路検出について~
はじめに ~この記事の経緯~
AtCoderで久々にBellman-Ford法を要求する問題が出題されました。Bellman-Ford法は蟻本でも紹介されている有名な単一始点最短経路アルゴリズムであり、負閉路の検出を行うこともできます。ところが今回扱う問題では、この負閉路検出の部分に工夫が必要です。過去にほぼ同様の問題が出題されたこともあり(D - Score Attack)、中~上級者にとっては難なく通されていました。ところがコンテスト終了後、Twitter上にそれらの提出の多く(本当に多くかは知りませんが)をhackするケースが現れ、議論が行われることになりました。本記事では、これらの議論をまとめることを目的としています。
問題
解法概要
解法としては、各辺のコストをからに変えるというものです。すると、このグラフの頂点から頂点までの最短距離の倍が答えとなります。負の重みをもつ辺があるので、Bellman-Ford法を使います。ところで、上述のように重みを変えたグラフについて、頂点から頂点のパス上に負閉路がある場合、ゲームのスコアを無限に大きくできるので、この場合はを出力するようにしなければいけません。
Bellman-Ford法とは?
そもそもBellman-Ford法ってなに?という方のために簡潔に紹介をします。詳細は他の蟻本や記事に委ねることにします。
アルゴリズムは以下のようになります。頂点数を、辺数をとします。また、辺の距離を頂点への現在の距離をとします。
回ループを回す。
- すべての辺について、ならば、とする。
- 回目にある頂点について、が更新された場合、負閉路が検出されたと返す。
が各頂点への最短距離である。
これで最短距離が求まることの証明は割愛しますが、負閉路検出について簡単に書いておきます。頂点のグラフにおいて、あり得る最大の負閉路に含まれる辺の数はです。従って、回目にある頂点について更新があったかどうかを調べれば、与えられたグラフ上に負閉路が存在するかどうかを判定できます。
本題 ~頂点から頂点へのパス上の負閉路検出~
ここからが本題です。頂点から頂点へのパス上の負閉路をどのように検出すればよいでしょうか。
誤解法1 普通にBellman-Ford法
普通にBellman-Ford法すれば終わりじゃないか、と思う方がいるかもしれません。しかし、上述のBellman-Ford法をそのまま適用すると、検出したくない負閉路も検出してしまいます。次の例を見てみましょう。 頂点がスタートで、頂点がゴールです。この例では、頂点と頂点を往復する負閉路が存在しますが、今回の場合では、最終的に頂点にたどり着ける閉路にしか興味がありません。しかし、Bellman-Fordによる通常の負閉路検出では、このような負閉路も検出してしまいます。工夫が必要です。
誤解法2 追加で回ループを回して頂点が更新されたかを見る
Twitter上で散見された誤解法のうち、最も多く見られたものです。まずこの解法の気持ちを説明します。
元々のBellman-Ford法では、負閉路検出のために、回目のループである頂点の最短距離が更新されたかをチェックしていました。今回知りたいのは、頂点から頂点へのパス上に負閉路があるか、つまりBellman-Ford法のループを何度も行ったときに、頂点の最短距離が更新されることはあるか、ということです。回目のループの際にある頂点の最短距離が更新されたとき、その影響が頂点に伝搬されるかどうかをチェックするには、最低であと何回ループを回せばよいでしょうか。負閉路の長さは最大であることから、追加で回行えばよさそうに思えます。従って、追加で回Bellman-Ford法によるループを回した後に頂点が更新されたかどうかをチェックすれば、目的を達成できそうです。
残念ながら、この解法は誤りです。次の例を見てみましょう。 この例で先に述べたアルゴリズムを用いるとどうなるでしょうか?頂点と頂点の間に負閉路が存在します。しかし、頂点の最短距離はですから、たった回のループでは当然頂点にはこの負閉路があるという情報は伝わりません。従って、このアルゴリズムは答えとしてを返し、無事Wrong Answerとなります。この例はが小さいですが、が大きい場合にはもちろん回もループを回すわけにはいきません。もう少し工夫が必要ということになります。
解法1
さて、ここから正しい解法の説明に入っていきます。誤解法2の問題点はどこにあるのでしょうか?それは、負閉路検出パートである頂点の最短距離が更新されたときに、実際に最短距離を正確に更新していることです。こうしてしまっているために、上に挙げた反例のように、辺の重みの差が極端な場合に、なかなか頂点の最短距離が更新されないという事態が起こってしまいます。
そこで、頂点に正確に最短距離に反映される代わりに「更新された」という事実のみを記録することにします。さらに、各ループ内で辺をチェックする際に、頂点が「更新された」という事実が記録されているなら、頂点にも「更新された」という記録を残すことにします。頂点の最短距離が更新されたならば、そこから伸びている辺の行き先の頂点のも、いつかは必ず更新されるという事実を伝搬させていくのです。このような伝搬を行えば、検出したい負閉路が存在する場合に、最大でも回のループで頂点に「更新された」という記録をつけることができます。またそのような記録がない場合は、検出したい負閉路は存在しなかったということになります。
以下の提出によって実装例を示します。頂点が「更新された」という記録をで管理しています。
Submission #6859372 - AtCoder Beginner Contest 137
解法2
解法1と考え方はほとんど同じですが、面白いと思ったので紹介します。誤解法2では、負閉路検出パートである頂点が更新された後の正確な最短距離を反映させていました。そうではなくて、更新があった場合にその頂点の最短距離をとします。すると、以後の更新では最短距離をとした影響が伝搬され、結果的に解法1と同じ挙動をすることになります。頂点の最短距離がであれば、検出したい負閉路が存在することになります。イメージとしては、負閉路を見つけたらその閉路だけ先に十分な回数更新を行っておく、というところでしょう。
実装例を以下に示します。負閉路検出のために新たに配列を用意したりする必要がなく、簡潔な実装になっています。
Submission #6860850 - AtCoder Beginner Contest 137
解法3
上の2つの解法とは異なる視点を持った解法です。現在の目的は、頂点から頂点のパス上に負閉路があるかを調べるということでした。つまり、そもそも頂点からたどり着けなかったり、頂点にたどり着けないような頂点には興味がありません。そこで、そのような頂点をあらかじめ削除しておくことを考えます。このためには、元のグラフの辺の向きをすべて反転させたグラフを考え、このグラフ上で頂点からたどり着ける頂点を列挙します。ここで列挙された頂点は、元のグラフにおいて頂点にたどり着ける頂点であり、それ以外の頂点からはたどり着くことができません。さらに、これらの頂点のうち頂点からたどり着けない頂点も削除します(頂点にたどり着けるが、頂点からたどり着けないような負閉路も検出してはいけないことに注意してください)。そして、この時点で残った頂点だけを見ながら通常のBellman-Ford法を行えば、検出された負閉路は頂点から頂点のパス上に存在するものだけであり、目的を達成することができます。こちらは直感的にわかりやすいかもしれません。実装例はAtCoderの解説放送をご覧ください(丸投げ)。
少し工夫が必要な負閉路の検出について紹介しました。果たして次にAtCoder上でBellman-Ford法が要求されるのはいつになることやら....。