競プロ典型90問 040

Get More Money（★7）

samekard

Published in

algorithm jp

Aug 19, 2024

注意

この記事は私の考察なので間違っていることがあるかもしれない。

問題の概要

家が何軒かある(最大100軒)。家の中にはお金があり、家に入って回収できる。出来るだけ多く集めたい。

ただし、

家に入るのにお金を払う必要がある。
家Yの鍵が家Xの中にある場合、家Yに入るには先に家Xに入って鍵をゲットしておく必要がある。この組み合わせがいくつかある。

また

家に入る料金はすべての家で同じ
家の中にある金額はそれぞれの家ごとに設定されている
X < Yである。例:家2の中に家5の鍵がある。

グラフ理論

この問題に必要なグラフ理論の知識をまとめる。

最大流問題

まずは最大流問題。開始頂点と終了頂点があるグラフに流れる値の最大値を求めるものである。最大流問題の一般的な解説はいろんなところにあるのでここでは割愛する。フォード・ファルカーソン（など）のアルゴリズムによって最大流を測定することができるが、それについても割愛する。

最大流問題のアルゴリズムは2つの値の小さい方を調べることが出来る

出来るだけ多く流そうとし、流れる量は詰まっているところによって決まる性質がある。これを利用すると、2つの値の小さい方を調べることが出来る。

この問題の解説に使うグラフの形

この問題では次のようなグラフを扱う。真ん中で真下に向かっている辺は容量が無限大。左に開始の頂点があり、右に終了の頂点がある。真ん中にいくつかあり、下方向であれば(隣に限らず)任意の場所に繋げることが出来る。

以降はこのタイプのグラフを前提とする。

余裕がある辺とない辺に分けることができる

（フォードファルカーソンなどのアルゴリズムで）最大流を測定した後、左右の辺は

能力に対して流量の余裕がある辺(more)
余裕がない辺(full)

にわかれる。ちなみに真ん中の辺は容量が無限大なので常にmoreである。

例をいくつか出す。数字は分母が容量、分子が流れている量を表している。

単純な性質の部分に分解する

通常はグラフが複雑になるが、単純な性質を持ち互いに影響の無い部分に分解できるとよいので分解する。ここでは、この部分をグループということにする。全体の流量はこの各グループの流量を足したものであれば、個々について考えてから足せばいいので何が起きているか把握しやすくなる。

このとき各部分の性質は

左がMORE
右がMORE
左右ともFULL

となるように分解する。

ここからは個々の辺の状態を表す場合を小文字でmore/fullとし、グループの性質を表す場合を大文字でMORE/FULLとする。

上の図では6つに分解されて、各性質の中に2つがある。

改めて性質を説明する。左がMOREは次の性質を持つ。

最大流を維持したままですべての左の辺（容量が0の辺を除く）はmoreにできる。ただし、すべて同時にではなく一つずつでよい。

というわけで、左がMOREでは、左の辺がすべてmoreというわけではなく、fullの辺も含まれてよい。

右も同様。

上流に左more、下流に右moreはあるか

ありえない状況をひとつ消しておく。上流に左moreの辺、下流に右moreの辺、の組み合わせはない。理由は、この組み合わせがある場合、アルゴリズムによってどちらか(あるいは両方)が限界になるまで辺に流れる値が大きくなっていき、このmore同士の組み合わせは解消されるから。

ここから分解の仕方を説明する。

moreの辺を見つける

最大流を測定した後、(真ん中の無限大を除く)すべての辺がfullであれば全体で「両方FULL」である。その場合、ここで分解終わり。

左にmoreの辺がある場合、そこから下に繋がっている部分は同じ左MOREグループに入る。このとき左の辺がfullでも左MOREに含める。左上のmoreの辺の流量をひとつ増やしてfullの辺をひとつ減らせば、この辺はmoreへの変更が可能だからである。

右にmoreの辺がある場合、そこから上に繋がっている部分は同じ右がMOREグループに入る。このとき右の辺がfullでも右がMOREに含めてよい。右下のmoreの辺の流量をひとつ増やしてfullの辺をひとつ減らせば、この辺はmoreへの変更が可能だからである。

反対方向へ拡張しながら縦の流れが0のところで切断する

左MOREは、ひとつ上から流れて来るものがある場合、ひとつ上も同じグループになる。その辺はmoreへの変更が可能だからである。

右MOREは、そこから下に流れているものがある場合、下も同じグループ。

流れが0で拡張できなければそこで終わり。

残ったもの

残ったものがある場合、それは両方FULLのグループになる。縦の流れが0のところで分割すると、両方FULLのグループは複数が連続することがある。

下流に左moreと上流に右moreはつながるか

もし下流に左moreの辺、上流に右moreの辺がある場合、どこかに流れが0のところがあるので必ず分解される。

流れ0のところがある理由は、下流に左more、上流に右moreで、その間に流れがある場合、最大流のアルゴリズムによって流れが0の状態にされるから。

この分解を気持ち悪く感じる人がいると思うが、今回の問題に当てはめると、家2の中に家5の鍵があり、家2に入るべきだが、家5に入るべきでない状況に該当する。

分解のパターンまとめ

流れを個々のグループに分解すると次のようになる。全部で7種類。なお、両方FULLはいくつか連続する場合がある。

真ん中の部分は一直線ではない

ここまでは一直線上に限定していたが、実際は縦方向の矢印の枝分かれがある。形が複雑になるとどんなことが起きるか考えてみる。

枝分かれがあるので手順を一つ追加する。次のように逆方向(上)に拡張した結果、順方向(下)への拡張を行う場合がある。

また並行状態の片方で左moreの辺、もう片方に右moreの辺がある場合、赤の部分の流れが0になるので、左MOREと右MOREはどちらも矛盾なく存在できる。赤の部分に流れがある場合、最大流測定アルゴリズムの実行時に解消するからである。

以上で、分割できることと分割の仕方の説明が終了（したはず）。

あとは、左MORE、右MORE、左右FULLの3つをそれぞれ単独で考えれば良い。

問題に当てはめる

左に家に入るときの料金、右に家に入ったときに得る金額。そして、Aに入ってBの鍵を得るときにAからBに無限大の辺を張ると次のようなものが出来る。

これに最大流問題のアルゴリズムを適用し最大流量を測定することでmoreとfullの辺を決定し、上で述べた分解を行うと、次の分析が出来る

家に入る料金がMOREのグループは、家に入る料金が高い。つまり入るべきでない
家の中で獲得できる料金がMOREのグループは、家の中で獲得できる料金が高い。つまり入るべき
両方FULLのグループは入っても入らなくてもどちらでもよい

答が出せそうな雰囲気がします。

答を出すような解釈を考える

ここまでは単純に「家に入るときの金額」と「家に入ったらもらえる金額」と「鍵の関係」を配置しただけなので答を出すようにする。

「取るべき行動」「グラフから得る値」「欲しい値」を整理すると

a > bのとき

行動：何もしない
グラフから得る値：b
欲しい値：0

a < bのとき

行動：家に入る
グラフから得る値：a
欲しい値：b — a

a = bのとき

行動：どちらでもよい
グラフから得る値：a(=b)
欲しい値：0

ということで、

b — グラフから得る値

とすれば欲しい値が得られる。

まとめ

左の辺を家に入る料金、右の辺を家の中にある金額とする
（鍵が存在する家）→（鍵を使用する家）の向きに無限大の辺を張る
最大流を測定する
入った時にもらえる金額の合計から測定値を引く

さいごに

「グラフ理論の層」と「グラフ理論をどう利用するかの層」に分けることがコツ

こういうタイプの問題を「燃やす埋める問題」というらしい