MM 135

iehn @arimasenu

MM135 やったこと mincostflowを適当なコストでS-a-b'-TとS-b-a'-Tで流し、制約を満たさない頂点を削除したり、辺のcapを減らしたりした。 辺のcapを減らした後に元のを使って高速に計算できればよかったと思うんだけど、やり方がわからず、試行回数が少なすぎて弱かった。

iehn @arimasenu

ACLを使ったので実装は楽だったが、中身を理解してないので調整ができなかった。

iehn @arimasenu

最初は適当に辺を壊しつつ伸ばしていって構築するのを考えたけど、明らかに実装が面倒なのでやめた。

TERRY @terry_u16

ちなみに弊社コン解説放送、なんとwataさんにご出演頂けることになりました。ありがとうございます……！ #AHC010 atcoder.jp/contests/ahc010 pic.twitter.com/fHnALCVIHf

拡大

コルン @colun

コドゲはどこへ行けば出来るんだろ。。。（死にかけてるので参加無理そうだけど。

コルン @colun

codingame.com/contests/sprin… これかな。

コルン @colun

11 DAYSか。参加するか。AHCのほうをキャンセル、、、Algo Artisできれば参加したいが。両方参加するか、、、？　二兎を追う者は、、、

コルン @colun

CodinGame用のメタヒューリスティクス、素案だけあって実装できてないので、そろそろ実装したい。（11日で実装できるのか問題はあるけど。

コルン @colun

コドゲの前に1時間寝る。。。というか、たぶん起きない。そのまま寝そう。

nejineji @shift_neji

ちょっと遅れましたがMM135おつかれさまでした。暫定16位みたいです。自分は2つの解法を使い分ける方針でした。 1. 全域木を少しずつ作っていき、その木を二部グラフだと思って二つの部分の次数の和が等しくなったときに、（辺を追加できるだけ追加してから）フローを流して最大マッチングを見つけ、

nejineji @shift_neji

そのマッチングと次数の和が一致すればそれが一つの答えなのでスコア最大のものを採用という作戦。 2. pathに長さ1の辺がいくつか加わったもの（画像の一番大きい連結成分のような感じ）に限定してAHC002のような感じでDFSで求める作戦。 pic.twitter.com/QFGpUYmo4p

拡大

nejineji @shift_neji

1の解法は木の成長の仕方を色々工夫したのですが、思ったよりも（最大マッチング）＝（次数の合計）となる条件が厳しく大きいケースではダメでした。何より計算が思い&フローを流してダメだった時に、どう辺を追加したり削除したりすれば答えに近づくのかというのがわからないのが大きそう。

nejineji @shift_neji

2の解法も探索できる解空間が狭く、やはり上位陣には届きませんでした。具体的には字数が大きいノードが固まっているところを突破できなかったです（先の画像の左側に7, 6, 9, 12が固まっているが、そのようなところ） 。それを突破するにはやはりサイクルや分枝が必要そう。

nejineji @shift_neji

1の方法でうまく行かなそうと気がついて2の方法に切り替えたのが締切2日前、改善の余地に気付きもしましたがちょっと時間など余裕がありませんでしたね。 また頑張ります。

nejineji @shift_neji

こういうのブログ作ってそこに書くべきでは？と思い始めた。

いなにわ @inani_waon

MM135を二部グラフにするの、 こういうケースでも出来るんだろうか。 ①②③ ④　⑤

もおあき @moooaki

なんか適当に見てたら、コドゲの言語アップデート出てきた。１時間前？？ codingame.com/forum/t/langua…

yowa @yowa

CodinGame、参加登録してた（記憶から抜けてた） twitter.com/yowa/status/15…

yowa @yowa

こどげ2022春、参加登録した。 4月22日から11日間っぽい Online programming contest and hackathon " CodinGame Spring Challenge 2022" | codingame.com/contests/sprin…

2022-03-16 23:43:10

海老コチニール @ebicochineal

コンテストページのF.A.Qの8くらいなのかなコード共有禁止について書かれてるの

yowa @yowa

こどげの時間だあああああああああああああ Online programming contest and hackathon " CodinGame Spring Challenge 2022" | codingame.com/contests/sprin…

nejineji @shift_neji

@inani_waon 私の解法の話ですかね。 全域木を少しずつ作るというのはプリム法をランダムにやるイメージで、一つ辺を追加するごとに次数の合計を計算をして、条件が満たされればフローを流す感じです。 この例だと例えば 3 3 - 5 3 - 5 - 4 2 - 3 - 5 - 4 と運良く成長すれば連結成分4の解が見つかります。

いなにわ @inani_waon

@shift_neji はい、コメントありがとうございます。 2-3-5-4だと偶数ですし良さそうなのですが、5頂点で1周するようなのは偶奇が上手く割り当てられるのかなーという疑問でした。（正直二部マッチという部分以外読み込み切れていないので、的外れだったらごめんなさい）

nejineji @shift_neji

@inani_waon あ、それは無理です。そういうケースは諦めます。 2部グラフのそれぞれのグループの次数の和の差が偶数だったら多い方のグループのノード間に辺を追加するみたいなことも考えましたが、深追いはしなかったです。

かえで @kaede20203

コドゲが始まるときって、こんなに楽しい雰囲気なのですね 知らなかった

yowa @yowa

こどげ、入力をエラーなく読み込むコードを書けたら、その時点で一仕事終えた感になって、他のことを始めてしまう