とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

Project Selection (燃やす埋める) 周りの話についてもう少し考えた

Competitive Programming Advent Calendar 2017 - Adventar　アドベントカレンダー最終日です。


先月はこの過激記事をご覧になった方も多いのではないでしょうか。 : 『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ

これについてもう少し色々な視点から整理したり、最近考えていた拡張を書いていきます。調査が不十分な点・誤植もあるかと思いますが、ご容赦ください。（誤植は教えていただけると助かります）
以下、Project Selection Problemは略してPSPとしておきます

また、前回の記事周りの話はそんなに面白くないので後回しにします。

拡張を考えていた話

モチベーション

私はPSPの信者なので、できるだけこれをサブルーチンとして利用することで、いい感じに問題を解きたいです。
しかし、イマイチ使い方がわからない問題があります。それが https://www.codechef.com/DEC14/problems/RIN この問題です。
想定解法では、面白いグラフの張り方をしています。知らない方はこの問題のeditorialをご覧ください。

ただ、今後紹介する方針ではなく、editorialにあるグラフの方が綺麗だと思います。

拡張

この問題をなんとかPSPの枠組みで解けるようにするために、PSPに対して次のような拡張をします。

プロジェクト i は集合 0,..., K-1 のうちのどれかの値が割り振られるとします。
このとき、p[i,0], ..., p[i, K-1] だけの利得がそれぞれ得られます。簡単のため、p[i, 0]=0とします。

また、プロジェクト i に k 以上の値を割り振れば プロジェクト j に t 以上の値を割り振らないと コストcが発生します。
プロジェクトに値を割り振ることで利得を最大化せよ。

これは一つのプロジェクトあたり、次のような利得と関係をつけたグラフをつけると表現できます。
矢印はINFコストを表現します。
f:id:tokoharu-sakura:20171224205019p:plain

一番左が選ばれるとその右がすべて選ばれるため、合計の利得はp[K-1]とみなせます。一番左を選ばず、その右が選ばれると合計利得はp[K-2]になります。どれも選ばなければ0( = p[0])です。このようなグラフを用意することで上記の拡張でも表現できることがわかります。

では、上記RINを解くときにはどうなるのか。必要なものは講義xの後に講義yを取る条件を入れ込むことです。
これは「講義xがk以上なら、講義yはk+1以上である。」という条件を各semester kに入れれば表現できます。

つまり、次のようなグラフを作るのがざっくりした方針になります。
f:id:tokoharu-sakura:20171224211542p:plain

細かいことを言うと、開講されていないsemester などを考慮する必要があるので、そういう頂点は利得を -M(Mは十分大きい定数)とする
などの工夫が必要と思います。その点で、想定解法より汚くなるかもしれません。

ただ、想定解法とは異なるグラフが構成できることは非常に興味深いです。

さらなる解釈

このような一般化PSPは次のことをしているとも思えます。

A[K-1] ⊂A[K-2]⊂ ... ⊂ A[0] であるときに、点x を 集合A[0]内に配置する。
点x をおいた場所が x ∈ A[i] ならq[i]点を獲得する

また、x が A[i]内にあるとき、 y はA[j] 内にいなければ c 点減点される。

これを見ると、集合の切り分け方が部分集合関係の鎖になっていることが本質的な気がしてきます。
そこで、次の問題を考えてみましょう。

3状態へ割り振るタイプの問題


いくつか前の記事でも登場しましたが、この問題で前節で紹介した切り分けが重要であることを確認します。

この問題が初見であれば、次のように、「燃やす集合」、「埋める集合」といった集合をそれぞれ作るアプローチを取るところから始めるのではないでしょうか。
f:id:tokoharu-sakura:20171224215219p:plain
実際こういった気持ちでスタートしてもPSPを構成できます(参考 : 続：『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ)が、片側の状態の01を反転する必要が出るため、なんだか奇妙でした。

しかし、先述した部分集合の鎖で考えることが自然だと思うと、次のように層を分けるのが自然そうに見えます。
f:id:tokoharu-sakura:20171224215503p:plain
つまり、（燃やす） ⊂ (埋めない) ⊂(全体)の関係です。
入れたい条件は、「xを燃やすならyを埋めない」の関係だったので、制約もちゃんと入れることができることがわかります。

TCO2017 Semifinal2 500 RatingProgressAward

これも何件か前の記事で紹介しました。（詳細は TCO2017 Semifinal2 500 RatingProgressAward - とこはるのまとめ）

この記事を参照すると、問題の言いかえは次のようなものでした。

ProjectをN個用意し、それぞれのProjectは proj[i]=0,1,2のように3値をとれるものとします。
このとき、a[i]からb[i]に到達可能ならproj[a[i]] >= proj[b[i]]を満たさなければならないとき、
proj[k]==1となるProject kに関して、change[k]の総和を最大化せよ。

この問題での集合の切り分けはproj[k] >= 2, proj[k] >= 1 とわけることが自然でしょう。

まず、「proj[k]==1となるProject kに関して、change[k]の総和」は
proj[i] >= 1ならchange[i]を足し、proj[i] >= 2ならchange[i]を引けばOK。

次に「a[i]からb[i]に到達可能ならproj[a[i]] >= proj[b[i]]」は
proj[b[i]] >= 1 ならば proj[a[i]]>=1,
proj[b[i]] >= 2ならば proj[a[i]] >= 2の制約を入れればOKです。

これだけわかれば解けてしまいます。
これでかなりお手軽に解けるようになったのではないでしょうか？

前記事の感想などを見て

色々思ったことを書きます。

前記事においてPSPの有用性を主張していました。
意図としては、

  • より思考をショートカットできるしお手軽な道具じゃないか？
  • ちゃんとこの辺りのテクにはそういう名前がついている

の周辺の2点を主張していたつもりでした。
これについて共感してくれる人が少なかったのはかなりショックでした。

ただ、この二点については考え始めるとどっちでもいいのかもという気持ちになってきました。

後者の名前は、twitterや会話における意思疎通において、解法のスケッチを伝える上で「燃やす埋める」は大変便利です。だからこれからも残り続けるでしょう。
ただ、PSP側も何か調べものをする意味で覚えておいて損はないとは思っています（マージテク <-> weighted union heuristics の関係に似ていると考えています）

前者のテクそのものとしての有用性は個人的には

  • 適当にグラフを作ると後からグラフを変形する可能性があるという点
  • 最大流の結果との定数を足し引きする整合性を管理するのが面倒

という二点が気がかりでした。
両方の懸念も、考え方に慣れればどうでもよさそうです。
個人的には最初はPSPの手順そのままに考えればミスも減るし入門として適していると考えてはいますが。

そもそも論として、強い言葉を使いすぎたのはまずかったです。

それから、skyさんのこのツイートにはかなり救われました。この場で感謝いたします。

最後に

この辺りの最大流のグラフの作り方は必ずしも一通りではないケースが多いと認識しています。綺麗なグラフで解けている場合もあれば、意味不明なグラフで解いているケースもあり、解答者が何を考えているのかわからないこともあります。
いろんな人がこの問題に興味を持てば色々な解釈がわかって面白くなる気がしています。実際、次の記事は私の一連の記事のあとに公開されました。最後の例が面白いです。
最小カットとProject Selection Problemのまとめ · うさぎ小屋

ところで、これは今回の話と無関係ですが、私は競技プログラミングに対して真っ当な努力はできていないので、今年のAdvent Calendarの記事も大変助かっています。今年も雰囲気でしか知らなかったテクをちゃんと知ることができて大変有益でした。多分世の中ガチ勢ばかりではなく、私みたいな人はたくさんいると思うので、来年のAdvent Calendarでも記事を書いてほしいです！

みなさんよいお年を！