-
masashinakata
- 1832
- 1
- 0
- 0
-
- いいね！0
iwashi31
@iwashi31
スレッドでマッチングの詳細聞かれたけど英語が無理なのでこれで許して…って言いながら図を貼った pic.twitter.com/4foUeYL0gQ
2021-08-06 13:01:40
拡大
いなにわ
@inani_waon
@fmhr__ マッチング計算時は全部無視しました。(個々のボールを動かすときのDFSでほんの少しだけ考慮しました) これはQuestions and extensionsスレッドでも聞かれている内容で、このスレで聞かれるということは実質不可能orとても高度な技術が必要という認識です。
2021-08-06 13:30:12
koyumeishi
@koyumeishi_
2部グラフの特性生かして cycle canceling で更新 O(n^2 * hoge) ぐらいにできないかなと調べたら、そもそも任意のグラフは2部グラフに変形できるから無理という話を見つけた (負閉路検出にO(n^3)かかるならハンガリアン法でいい) (今回のは枝刈りすれば大丈夫そう) cs.stackexchange.com/questions/1057… twitter.com/iwashi31/statu…
2021-08-06 13:37:58
iwashi31
@iwashi31
MM128 のマッチング、最小費用流は色ごとに 1 回やるだけで、ボール動かし中は任意の同色ボールのペアについて目的地を入れ替えて距離が縮むなら採用するは常にチェックするようにしていた
2021-08-06 11:06:08
iwashi31
@iwashi31
二部マッチングの辺のコストに distance と書いたけど、正確には距離の 2 乗の値を使っている。マンハッタン距離で最適化をしようとすると直感的に嫌な気持ちになったので twitter.com/iwashi31/statu…
2021-08-06 13:41:35
koyumeishi
@koyumeishi_
Dynamic Hungarian Algorithm とやらで更新 O(k * n^2) というのも見つけた (kは更新された行,列の数) ri.cmu.edu/pub_files/pub4…
2021-08-06 13:43:18
iwashi31
@iwashi31
これかなり面白くて、最終的に魚になった twitter.com/togatoga_/stat… pic.twitter.com/HEIOabHjij
2021-08-06 19:38:37
拡大
かえで
@kaede20203
できあがりの盤面を4つ作って、そこにボールを移動させてみました。まだまだ無駄な動きが多かったです。 pic.twitter.com/YBTMAPhFT8
2021-08-06 21:13:04
拡大
iwashi31
@iwashi31
入力ミスで謎の “H ex” というお題が飛んだ後渾身の “H ex” が描画されて出てきたのもめちゃくちゃ笑った pic.twitter.com/FkswPV62fB
2021-08-06 22:32:23
拡大
拡大
yowa
@yowa
MM 128、 submission review で自分の system test の結果があるのを確認。 テストケース 1000件中 174件が 10ms 以内、418件が 100ms 以内で終わってて、ちゃんと時間使えよという話だった
2021-08-07 08:10:10