TCO18 MM R1 - RoadsAndJunctions

mamekin @mamemame_fujita

山登り法を実装後は失敗確率について考えてみる。 失敗確率が高いとせっかく探索した候補点が無駄に終わってしまうので、 ほぼ同じ位置に点を重ね置きするアルゴリズムを検討・実装してみたら、 それなりに点数が上がってハイテンション。（ただし、ここがピーク）

mamekin @mamemame_fujita

それからは、期待値最大となるように各位置での点の個数をDPで求めてみたり、 ランダムな3点に対するフェルマー点を正確に求めて候補点として使ってみたり、 四角形に対するシュタイナー木を構築するために点を同時に2つ追加してみたり…

mamekin @mamemame_fujita

色々やったが後半は失速してしまい点数が全然伸ばせなかった。 とりあえずこれからタイムライン遡って他の人の解き方を見てみようかな。

hakomo @hakomof

best/yourより(best/your)^2のほうが分散のweighが大きいというの、期待値の悪化量より分散の上昇量が大きくないとペイしない。だから期待値の最適化が最適なこともあるよね（この問題はどうだったのでしょう

mamekin @mamemame_fujita

ドロネー図については、下記のスライドを参考にしようとしたんだけど、三角形に対して気構造を作るという点が理解できなかった。 slideshare.net/Kinokkory/ss-2… 分割統治法でも同じ計算量でできるっぽいが、どちらにしてもアルゴリズムが分からない。

koyumeishi @koyumeishi_

そういえば言及してる人を見なかった気がするけど、 N点からの距離和が最小になる点 geometric median なる概念があるらしくて (3点の場合フェールマー点が相当)、凸関数だから勾配方向に適当に動かしてやればコスト最小は割とすぐ見つけられる en.wikipedia.org/wiki/Geometric…

はまー @yuuki3655

Junctionを新たに作ってもグラフの構造はほとんど変わらないので、スコアの変化量をキャッシュして再利用してた。新たなJunctionによって辺が変わるところの近傍(使われてる辺の最大長)だけ再計算とかした。

starwand @__starwand

最初の1000シードのFailure Probability, NC, S, raw score, に対するスコア分散のプロット(平均スコアに対する各スコアの比率の分散: N=1000)。分析はできてない。本番のスコア計算でどのくらいぶれるのか見たほうが良かったかもしれない pic.twitter.com/jAiB8vuEAh

拡大

拡大

拡大

拡大

starwand @__starwand

分散0のはSが小さいときに多いから、難しくて置かない判断してるケースかな。これもしかして本番のスコア計算で置きに行ったほうが期待値上がるのかな。。

starwand @__starwand

解が弱い(スコアが上がる置き場があるのに見つけられてない)、ギリギリ置けるところを諦めてる、本当に置かないほうがいい、のどれかかな。前者の可能性も大きい気はするけど、それならそれで差がついてるポイントだから確認しなきゃだめだった

starwand @__starwand

スコアが下がる置き場、のまちがい

starwand @__starwand

個別に見ないとわかんないな。あとビルド数に対してもプロットすべきだった

starwand @__starwand

分散0は一度も失敗してないってことだから、置いてないケースか。てことはbuildCost/Sに対しても見てみたほうがよさそう

phyllo(フィロ) @phyllo

クラスカル法、辺がN-1本追加したら終了するとしないとだと違うよ、という話題で、対して変わらないのでは？と思ってたけど、UnionFind問い合わせがあるので、やってみると焼きなましの回数3倍ぐらいになってほげだった(1行追加するだけ)

phyllo(フィロ) @phyllo

ということで、張ってきます。今回のマラソンマッチの参加記。 TCO18 MM R1 RoadsAndJunctions - phyllo’s algorithm note phyllo-algo.hatenablog.com/entry/2018/05/…