MM 120

yowa @yowa

寄せるのが √N 個なのは、(X=1 で) m 個寄せるのに O(m^2) のコストかかるから、と理解。 （その理屈だと√Nの（何かしらの）定数倍になりそうだし、 X≠1 だと 1/2 乗じゃない何かになりそうだけど、しーらない）

yowa @yowa

隣接要素の差を減らすヤツ、他の作業中にチラっと浮かんだことが何度かあったけど、その作業が一区切りつく前に頭から消えちゃって、結局実装するには至らなかった

c7c7 @C7C7LL

MM120 1、各数字の最終位置と、マージする順番を山登り (Xが小さい時用) 2、幅10以下に関して、(転倒数^2)/pow(幅,X)が最小になる操作を貪欲に繰り返す (Xが大きい時用) の2つを実装してみたけどダメでした。 どうやって、良い感じに巻き込みながら回転するかを考え始めたら頭壊れました。

c7c7 @C7C7LL

上位の解法見ると巻き込みは気にせず良い感じの貪欲をしてる? 今回の問題 計算量がきつすぎて何も分からなかった

c7c7 @C7C7LL

1.5<X<2.5 くらいの時の良い感じの動かし方が全く想像できなかったので負けです

onodera @0verfit

halite 1位ってdeepmindの人じゃん…納得

yowa @yowa

小さい N で最適解を出してそれを眺めてアイデアを思いつこう、とか思ってたけど結局やってないな…

yowa @yowa

出力例 (-seed 1000 -X 1.0 -N 200 -K 200 / Score = 2865.0) pic.twitter.com/2e9PY9Fx6M

拡大

yowa @yowa

（文脈がヘンになったけど、この画像は全然最適解じゃ）ないです

yowa @yowa

あー 寄せるヤツを0、それ以外を1とすることで K=2 の問題に置き換えられて、K=2 で効率的に解く方法を適用すると、O(m^2) も掛からなくなって普通に同じサイズで二分割の分割統治ができるんかー

yowa @yowa

↓が、Score = 2427.0 になった twitter.com/yowa/status/13… pic.twitter.com/SxpdI6Cb21

拡大

yowa @yowa

色のグラデーション、赤→緑→青じゃなくて、赤→青みたいに2色で十分、というかそっちの方がみやすいな？

海老コチニール @ebicochineal

なんかしんどい 今回のマラソン納得のいくスコアが出るまでやり続けるか、エビで何か作るかしないと回復しなさそう

Kojima @t33f

MM120, X<<1 のときはうまくやると N/2 ぐらいのスコアにできるんじゃないかと思ったんだけどやり方わからん

iehn @arimasenu

MM120 やったことなど(適当に書いたら情報量があまりない感じになった) ideone.com/MVlGPp