SoundHound Inc. Programming Contest 2018 (春)
-
masashinakata
- 3783
- 0
- 0
- 0
-
- いいね！0
けんちょん
@drken1215
こないだのサウコンで出題されたので、二部グラフの最大安定集合、最小点被覆、最小辺被覆についてまとめてみました！！！ 自分にとってもすぐ便利に参照できるように「早見表」をつけました。内容としては蟻本 P.199 に書いてあることを行間を埋めて整理した感じです。 qiita.com/drken/items/7f… pic.twitter.com/XhReXdPM2T
2018-01-29 21:34:41
拡大
jajack
@jajack000
@drken1215 いいね。どうもです。２分マッチングの記事見ました！DPの記事も気になったので見てみます。よろしくお願いしまーす。
2018-01-29 22:13:38
jajack
@jajack000
@drken1215 フォロバありがとうございまーす。 これからもいい記事を期待しています。２分マッチング。図があるのはすごく良い！！
2018-01-29 22:21:54
けんちょん
@drken1215
大体蟻本に書いてあるじゃんと言われればその通り (一応二部グラフの最大安定集合がなぜ最大マッチングで求められるかを書いた) なんだけど、蟻本の内容を行間を埋めて整理した記事の需要にはなんとなく気付いてるのん。
2018-01-29 22:24:43
けんちょん
@drken1215
@wkbme ありがとめる！！ 最大マッチングの部分は迷っためる。それについては無限に記事も資料もあるからいいかなと思っためる。
2018-01-30 01:22:36
若葉めるる@微分コンサル
@wkbme
@drken1215 なるほどめるね～。安定集合と点被覆の２つは早めの段階で用語解説あった方がいいと思った！（というか、”安定集合”という概念がサウハンCそのものなんだね！）
2018-01-30 01:33:31
若葉めるる@微分コンサル
@wkbme
@drken1215 ところで、記事とは関係ない話になるんだけど、C問題を二部グラフに書き換えるときってどう考えるんや？人のsubmittionみても”二部”に考えているようには見えなかった・・・。
2018-01-30 01:48:47
けんちょん
@drken1215
@wkbme 修正してみたのん！！！！！！！ これでだいぶよくなったかな？？？ qiita.com/drken/items/7f…
2018-01-30 02:37:52
けんちょん
@drken1215
@wkbme あれ、人の submission は二部グラフじゃないのかな... グリッドの各マスは座標 (i, j) みたいに表すことができて、これを 左ノード i と右ノード j を結ぶ辺 に対応させるテクニックなのん！！！
2018-01-30 02:41:51
若葉めるる@微分コンサル
@wkbme
@drken1215 いくつか見てみたけど、隣接リストでやっている人がおおかっためる！隣接していたら反対の部（用語間違ってる？）になることがわかるから、その上で最大マッチ作ってる感じみたい
2018-01-30 02:58:19
けんちょん
@drken1215
@wkbme あ、それは多分、二部グラフの最大マッチング問題を、スーパーノードを付け加えたグラフ上の最大流問題に帰着してるめるね！！！
2018-01-30 03:03:58