TCO18 MM R1 - RoadsAndJunctions
-
- いいね！0
chokudai(高橋 直大)@AtCoder社長
@chokudai
MM終了お疲れ様でした。「候補点の列挙」と「点の選択」の２パートに分かれると思っていて、どちらも0.1秒解と1時間解の出力が変わらない状態に陥っていて、それが5日間改善しない、みたいな絶望的な状況だった。どこらへんで差がつくの・・・？
2018-05-17 10:04:10
chokudai(高橋 直大)@AtCoder社長
@chokudai
とりあえずseed1101あたりのスコア期待値を教えてもらえると・・・。（多分こういう候補点が多いケースしかないんだろうけど、何やっても一生スコアが上がるケースが見つけられなかった）
2018-05-17 10:06:41
chokudai(高橋 直大)@AtCoder社長
@chokudai
これ全く意識してなかったけど40位くらいの段階で意識するものではない気がする・・・！ twitter.com/colun/status/9…
2018-05-17 10:07:37
ふぁる
@fal_rnd
最初重心かなと思ってた(雑魚)→調べる→フェルマー点?→シュタイナー問題? →三角形のboundingrect全探索でもだいぶ速いからいいや
2018-05-17 10:07:38
tomerun
@tomerun
TCO18 Marathon Round1おつかれさまでした。期待値を評価しながら交差点位置を焼きなましました。なんで人々のスコアがあんなに上下動してたのかわかってない
2018-05-17 10:10:13
chokudai(高橋 直大)@AtCoder社長
@chokudai
ちなみに候補点列挙を７通りくらい書いて、焼きなましとビームサーチを書きました。焼きなましでたどり着けてない解にビームサーチでたどり着くのかなと思ったら全然そんなことはなく、ひたすらそんな迷走を繰り返していた。
2018-05-17 10:11:38
コルン
@colun
上位がなぜ乱高下するかというと、基本的にyour/bestの最小化と比較してbest/yourの最大化はvolatilityが高い解を出す必要があり、更に(best/your)^2だともっとvolatilityの高い解が必要になるためだと思われます。つまり、上位は、乱高下するのが本来的には正しい、、、はず。
2018-05-17 10:12:23
たけのじ
@kt_tenel
TCOR1お疲れ様です 暫定118位でした。 まずCitiesだけでMSTをつくって、三角形や四角形に一辺足りない状態になってる部分にシュタイナー点としてjunctionをつくって貪欲 五角形もやるべきだったけど疲れたので…
2018-05-17 10:12:40
koyumeishi
@koyumeishi_
そんなことより分割統治 O(N log N) ドロネー三角形分割作ったから見て pic.twitter.com/yVYsg3bzVe
2018-05-17 10:13:11
chokudai(高橋 直大)@AtCoder社長
@chokudai
あーやっぱ普通に負けてる気がする （自分のだと4534くらいだった） twitter.com/tomerun/status…
2018-05-17 10:16:34
tomerun
@tomerun
seed1101 交差点46個、スコア期待値4531.8749 （右は交差点0個の場合ね） pic.twitter.com/m5kr2nqkzR
2018-05-17 10:12:09
Shuichi Tamayose
@_simanman
最初は以下の処理を繰り返し 1. 交差点を良さそうなところに設置 2. 微調整 （山登り) 終わったらロストすると困る交差点を多重化しておく。 最小全域木問題解いて終わり
2018-05-17 10:16:49
kimiyuki@うさぎ🐇
@kimiyuki_u
結果は散々だったけどjunctions設置時の点数差分のheatmapは面白いので見て pic.twitter.com/5nJqqTOSMQ
2018-05-17 10:17:27
nico_shindannin（診断人）
@nico_shindannin
最低限の追い込みはできたけど、根本的になにか気づいてなさそう ・フェルマー点追加、３辺足して隣接する辺のみカット→130位 ・隣接する辺とか気にせずカット→80位 ・ジャンクションやすいときは、フェルマー点付近に多めに都市を足す→60位
2018-05-17 10:18:03
yowa
@yowa
マラソンやったこと： - 交差点の候補を列挙（ドロネー分割して各三角形や隣接三角形を合わせた四角形に対していい感じな点）。 - 各点ごとに単体でのスコアを計算 - 競合しない点だけを併合していく(A*で時間うちきり) - 失敗確率高いなら同じ点を（ちょいズラして）重複させることも考慮
2018-05-17 10:18:44
nico_shindannin（診断人）
@nico_shindannin
・有力な頂点追加パターンに関して、上位12総当たり→ほぼかわらず ・4辺追加→ほぼかわらず （2頂点&4辺追加は試せず終わる） で終了しました…。 今回すごく出遅れたけど、なんとかやりたいなぁと思ってたことは1度はだいたい試せたので、実力不足じゃ・・・
2018-05-17 10:20:15
iehn
@arimasenu
MM終わってた。後半はバグらせることしかできず、提出できなかった。 生のscoreの最大化は、幾何と確率が得意な人ならアルゴリズムの問題として解けるんちゃうんかとしか思えなかったので、この問題はライトニングだろと思ってた。
2018-05-17 10:21:25