TCO18 MM R1 - RoadsAndJunctions
-
- いいね！0
kimiyuki@うさぎ🐇
@kimiyuki_u
MMが迷走した結果として半分kaggleみたいなことになってた pic.twitter.com/wcy3MoTJNb
2018-05-17 10:23:21
拡大
拡大
拡大
拡大
iehn
@arimasenu
ただ、自分は幾何ができないので、すべての点で配置した時のscoreを出した。2つの点を置かないとscoreが良くならないケースは考えてないのと、リーダーボード上でのscoreは違うので良い計算方法がわからなかった辺りが、上位と差がありそうな箇所。
2018-05-17 10:23:48
yowa
@yowa
seed: 1008。J3,4,5がほぼ同じ場所に置いてるけど（failure対策）、これはもっと違う場所に置くのが正解のケース多いなあと気付いたのが昨夜だったので間に合わず pic.twitter.com/ffKIDqwXtK
2018-05-17 10:26:32
拡大
keymoon
@kymn_
MM、とりあえず三角形においてのフェルマー点それぞれにおいての点の期待値を出して大きいのを出した いくつかの三角形を四角形に併合して、四角形の重心にした方が良さそうだった(多分ここがマラソンフェーズ
2018-05-17 10:29:09
コルン
@colun
seed=1008は、こんな感じでした。(3)っていうのは、そこに3つ置きますよーって感じ。右下の緑は2つあるけど、うまく統合できていないね。。。 pic.twitter.com/jkkYCqG3Ao
2018-05-17 10:33:42
拡大
yowa
@yowa
今回のマラソン問題を失敗確率0、コスト0にすると、(Euclidean)シュタイナー木で、それでも NP-hard という理解。 | Steiner tree problem - Wikipedia - en.wikipedia.org/wiki/Steiner_t…
2018-05-17 10:34:04
kuuso
@kuuso1
MMお疲れさまでした。 ドロネー分割して各三角形内の最小点を列挙して組み合わせて初期解を作って焼きなましで調整した。provisional86位くらい？
2018-05-17 10:35:23
chokudai(高橋 直大)@AtCoder社長
@chokudai
colunさんの見た感じ、自分は候補点列挙を先にやった結果、「候補点と他の点の３点を結ぶやつ」みたいなのを作れてなくて、これが敗因の１つかな、とちょっと思ってる。 pic.twitter.com/2BDWVpIEjM
2018-05-17 10:36:21
拡大
kuuso
@kuuso1
持っててよかったコンピュータージオメトリ。 ドロネー分割の計算量保証にオイラーの多面体定理つかわれてて感動したので、これからのトポロジーの教科書でも紹介してほしいくらいだ。
2018-05-17 10:41:47
chokudai(高橋 直大)@AtCoder社長
@chokudai
あ、２乗だから細かい差の影響出やすいのか（２乗だって気付いてないから「どう考えても足りないー」って色々模索してたのが完全に裏目に出ている）
2018-05-17 10:45:39
fmhr__
@fmhr__
junctionのおきもちになって junctionCost *= 1 + failureProbability + 0.0001;
2018-05-17 10:47:11