ABC137-E:Coins Respawn ~負閉路検出について~

はじめに ~この記事の経緯~

 AtCoderで久々にBellman-Ford法を要求する問題が出題されました。Bellman-Ford法は蟻本でも紹介されている有名な単一始点最短経路アルゴリズムであり、負閉路の検出を行うこともできます。ところが今回扱う問題では、この負閉路検出の部分に工夫が必要です。過去にほぼ同様の問題が出題されたこともあり(D - Score Attack)、中~上級者にとっては難なく通されていました。ところがコンテスト終了後、Twitter上にそれらの提出の多く(本当に多くかは知りませんが)をhackするケースが現れ、議論が行われることになりました。本記事では、これらの議論をまとめることを目的としています。

問題

E - Coins Respawn

解法概要

 解法としては、各辺のコストをc_iからP-c_iに変えるというものです。すると、このグラフの頂点1から頂点Nまでの最短距離の-1倍が答えとなります。負の重みをもつ辺があるので、Bellman-Ford法を使います。ところで、上述のように重みを変えたグラフについて、頂点1から頂点Nのパス上に負閉路がある場合、ゲームのスコアを無限に大きくできるので、この場合は-1を出力するようにしなければいけません。

Bellman-Ford法とは?

 そもそもBellman-Ford法ってなに?という方のために簡潔に紹介をします。詳細は他の蟻本や記事に委ねることにします。
 アルゴリズムは以下のようになります。頂点数をN、辺数をMとします。また、辺u,vの距離をc_{u,v}頂点vへの現在の距離をd_vとします。

  • N回ループを回す。

    • すべての辺(u,v)について、d _ v \lt d _ u+c _ {u,v}ならば、d _ v = d _ u+c _ {u,v}とする。
    • N回目にある頂点vについて、d_vが更新された場合、負閉路が検出されたと返す。
  • d_1,\cdots,d_Nが各頂点への最短距離である。

 これで最短距離が求まることの証明は割愛しますが、負閉路検出について簡単に書いておきます。N頂点のグラフにおいて、あり得る最大の負閉路に含まれる辺の数はNです。従って、N回目にある頂点vについて更新があったかどうかを調べれば、与えられたグラフ上に負閉路が存在するかどうかを判定できます。

本題 ~頂点1から頂点Nへのパス上の負閉路検出~

 ここからが本題です。頂点1から頂点Nへのパス上の負閉路をどのように検出すればよいでしょうか。

誤解法1 普通にBellman-Ford法

 普通にBellman-Ford法すれば終わりじゃないか、と思う方がいるかもしれません。しかし、上述のBellman-Ford法をそのまま適用すると、検出したくない負閉路も検出してしまいます。次の例を見てみましょう。 f:id:sigma1113:20190811165053p:plain 頂点1がスタートで、頂点4がゴールです。この例では、頂点2と頂点3を往復する負閉路が存在しますが、今回の場合では、最終的に頂点4にたどり着ける閉路にしか興味がありません。しかし、Bellman-Fordによる通常の負閉路検出では、このような負閉路も検出してしまいます。工夫が必要です。

誤解法2 追加でN回ループを回して頂点Nが更新されたかを見る

 Twitter上で散見された誤解法のうち、最も多く見られたものです。まずこの解法の気持ちを説明します。
 元々のBellman-Ford法では、負閉路検出のために、N回目のループである頂点の最短距離が更新されたかをチェックしていました。今回知りたいのは、頂点1から頂点Nへのパス上に負閉路があるか、つまりBellman-Ford法のループを何度も行ったときに、頂点Nの最短距離が更新されることはあるか、ということです。N回目のループの際にある頂点の最短距離が更新されたとき、その影響が頂点Nに伝搬されるかどうかをチェックするには、最低であと何回ループを回せばよいでしょうか。負閉路の長さは最大Nであることから、追加でN回行えばよさそうに思えます。従って、追加でN回Bellman-Ford法によるループを回した後に頂点Nが更新されたかどうかをチェックすれば、目的を達成できそうです。

 残念ながら、この解法は誤りです。次の例を見てみましょう。 f:id:sigma1113:20190812102459p:plain この例で先に述べたアルゴリズムを用いるとどうなるでしょうか?頂点2と頂点3の間に負閉路が存在します。しかし、頂点4の最短距離は-100000ですから、たった4回のループでは当然頂点4にはこの負閉路があるという情報は伝わりません。従って、このアルゴリズムは答えとして100000を返し、無事Wrong Answerとなります。この例はMが小さいですが、Mが大きい場合にはもちろん100000回もループを回すわけにはいきません。もう少し工夫が必要ということになります。

解法1

 さて、ここから正しい解法の説明に入っていきます。誤解法2の問題点はどこにあるのでしょうか?それは、負閉路検出パートである頂点の最短距離が更新されたときに、実際に最短距離を正確に更新していることです。こうしてしまっているために、上に挙げた反例のように、辺の重みの差が極端な場合に、なかなか頂点Nの最短距離が更新されないという事態が起こってしまいます。
 そこで、頂点vに正確に最短距離に反映される代わりに「更新された」という事実のみを記録することにします。さらに、各ループ内で辺(u,v)をチェックする際に、頂点uが「更新された」という事実が記録されているなら、頂点vにも「更新された」という記録を残すことにします。頂点uの最短距離が更新されたならば、そこから伸びている辺の行き先の頂点のも、いつかは必ず更新されるという事実を伝搬させていくのです。このような伝搬を行えば、検出したい負閉路が存在する場合に、最大でもN回のループで頂点Nに「更新された」という記録をつけることができます。またそのような記録がない場合は、検出したい負閉路は存在しなかったということになります。
 以下の提出によって実装例を示します。頂点vが「更新された」という記録をnegative_vで管理しています。
Submission #6859372 - AtCoder Beginner Contest 137

解法2

 解法1と考え方はほとんど同じですが、面白いと思ったので紹介します。誤解法2では、負閉路検出パートである頂点が更新された後の正確な最短距離を反映させていました。そうではなくて、更新があった場合にその頂点の最短距離を-\inftyとします。すると、以後の更新では最短距離を-\inftyとした影響が伝搬され、結果的に解法1と同じ挙動をすることになります。頂点Nの最短距離が-\inftyであれば、検出したい負閉路が存在することになります。イメージとしては、負閉路を見つけたらその閉路だけ先に十分な回数更新を行っておく、というところでしょう。
 実装例を以下に示します。負閉路検出のために新たに配列を用意したりする必要がなく、簡潔な実装になっています。
Submission #6860850 - AtCoder Beginner Contest 137

解法3

 上の2つの解法とは異なる視点を持った解法です。現在の目的は、頂点1から頂点Nのパス上に負閉路があるかを調べるということでした。つまり、そもそも頂点1からたどり着けなかったり、頂点Nにたどり着けないような頂点には興味がありません。そこで、そのような頂点をあらかじめ削除しておくことを考えます。このためには、元のグラフの辺の向きをすべて反転させたグラフを考え、このグラフ上で頂点Nからたどり着ける頂点を列挙します。ここで列挙された頂点は、元のグラフにおいて頂点Nにたどり着ける頂点であり、それ以外の頂点からはたどり着くことができません。さらに、これらの頂点のうち頂点1からたどり着けない頂点も削除します(頂点Nにたどり着けるが、頂点1からたどり着けないような負閉路も検出してはいけないことに注意してください)。そして、この時点で残った頂点だけを見ながら通常のBellman-Ford法を行えば、検出された負閉路は頂点1から頂点Nのパス上に存在するものだけであり、目的を達成することができます。こちらは直感的にわかりやすいかもしれません。実装例はAtCoderの解説放送をご覧ください(丸投げ)。

 少し工夫が必要な負閉路の検出について紹介しました。果たして次にAtCoder上でBellman-Ford法が要求されるのはいつになることやら....。