Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

牛ゲーの解法

スマホゲームを作ったり他のブログをやってたら2ヶ月間、競プロの勉強から離れていて、戻ってみたら牛ゲーのことすらすっかり忘れていたのでここで復習しておきます。(ものは忘れかけた頃に復習するのが良いのです。2ヶ月も開けたのは意図的です)

牛ゲーというのは、

D - People on a Line

のように、一列に並んでるものの距離に何か制約がある問題のことです。牛ゲーと呼ばれる所以は、蟻本の2-5に、一列に並んだそれぞれの牛の最小距離と最大距離が与えられた時の最初と最後の牛の距離を求める問題に由来します。

このAtCoderの問題であれば、重み付きUnion Find木を使って解けます。情報を使っていって、木に連結されている場合に、実際のポテンシャル差と違う場合にNoと表示すれば良さそうです。

もっと直接的な問題としては

https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B

があります。

牛ゲー自体は、最短路の問題に帰着させてしまうことが出来ます。

「最短路を求めるアルゴリズムの本質を理解した上で、そうとは見えない別の問題に応用する」というのはたまにあるようで、一言でいうと

d[i] + w >= d[j]に帰着させるということです。

牛ゲーでは、

  • d[j] - d[i] >= w
  • d[j] - d[i] <= w

が与えられますが、それぞれ最短路の式に帰着出来るよう変形すると

  • d[j] - w >= d[i]
  • d[i] + w >= d[i]

となります。つまり、負の距離を許すベルマンフォード法で解くグラフに帰着すればよいことがわかります。

ベルマンフォード法は、d[j]を確定させる際に、全エッジについて、d[i]からw足した値がd[j]より小さくならないかを調べていくというものです。これで、更新が止まるまでぐるぐる回すため、オーダーはO(VE)になります。

ダイクストラ法は、負の距離を許さない場合、「毎イテレーションごとに最小距離のノードは、そのノードについて最終的な最小距離である」という性質を利用します。これは、距離が正なため、他のノードを迂回したとしても、今より小さい距離が得られないからです。この実装として、プライオリティキューを使ったものが用いられることがあります。