またもったいないことをしたのかもなぁ。解法を一言くらい盗み見し、PSP という問題だということがわかった。 一応、Ad-hoc ではなく典型なものであったので、思いつかなくても仕方ないが、もう少し考えるべきだったか。
この問題は、レベルという概念を少し置き換えるだけで PSP になる。 あるアチーブメントがあるスキルをあるレベルまで要求する場合、そのスキルに対応するノードをレベルごとに用意し、 要求するレベル以下のものすべてに無限大の辺を貼ることによって単純な PSP 問題になる。 今回考えるのは、"選ばない", "コストを払って選ぶ" というのを最小化する問題になっている。
まず PSP (Project Selection Problem) について何もわからなかったので、調べた。 どうやらあるプロジェクトにはある製品たちが必要で製品を購入してプロジェクトを選ぶか、購入しないでプロジェクトを選ばないかで ある利益を最大化する問題みたいである。
これを解くには、まず全プロジェクトを選ぶのを初期状態とし、その状態から選ばないというコストと、製品のコストを払って選ぶかにすると、 そのコストを最小化する問題に帰着する。そしてこれが最小カットを求めることで解けるようだ。 グラフの条件設定として、あるプロジェクトを選ばないことで製品を購入するパスを削除できるようなものに誘導していく。 逆もしかりである。製品を購入するとそのプロジェクトに対してパスが存在しなくなるようにする。 これは"プロジェクトを選ばないあるいは製品を選ぶ"という辺をカットするのと同じことである。
こうするとどうなるかと言うと、あるノード $s$ からプロジェクトに対応するノードにそれぞれ選ばないことで生じるコストの辺を張り、 そのプロジェクトから必要な各製品に対して無限大の辺を張り、各製品からあるノード $t$ に製品のコストの辺を張るということで実現できる。 これは必要な製品を購入するあるいはプロジェクトを選ばないという処理でそのプロジェクトについての演算が終了する事を意味するような 辺の張り方になる。製品の購入がダブることもないのでなるほどこういう形で解けばいいのかという感じである。
まあそのように張ると最小カット問題に帰着できるので、これを最大流で解いて、終わりというわけである。
なにかの物に対して、選択肢があって何かを選べば処理完了になるようなものについて、最小カットが使えるなと思った。 そのものに対してパスを切る事を考えると、辺がそれぞれの条件になる、みたいな。
あと、よく最小カットの図の説明について、平面グラフが使われていて、これを線を使って斬るような説明がされているものがあるが、 実際は 2 次元の線で斬るようなやり方で描けないこともある。 とにかく最小カットで大事なのは、パスを無くすことである。だから辺を削除することを念頭に置いて考えていったほうがいいように思う。
最小カットの辺の張り方がやや違うので、同じことをやっているようには見えない。 今回の問題は PSP で解けると言えるのはわかるが、燃やす埋めるで解けるという言い方ができるのかがちょっとわからない。 もうちょっと理解を深めたら関連性についてわかるのかもしれないが。
Dinic を使って実装。結構単純な実装だと思う。
もはや感想は書ききったようなものだが、PSP とか知らない単語が解法だった時に調べたほうがいいのかそうでないのか。 PSP を再発明しようなんて、ちょっとできるものなのかもわからない。ABCは典型問が主なので、知らないなら調べたほうがいいのかな。 今回は PSP がわかっていれば(PSPだと見抜くフェーズもかなり難しいかも知れないが)、簡単にグラフが作れる問題ではあったので、 単に道具として調べたほうがいいのかとは思った。
今回の問題を通じて、最小カット問題に帰着することで解ける問題の形を少し理解できたなと思った。
(2023/10/29 12:13)