MM107参加記

ラソンマッチにおそらく初めて最初から最後までちゃんと取り組んだら実力に見合わない結果が出たので何をやったのかの記録


f:id:gasin:20190131153514p:plain
standings

 多くの人は別のこともしながらMMをしているはずなので、ずっとMMをしていた僕が有利なのはそれはそうなのだけど、それでもうれしいっちゃ嬉しい。
 てわけで何をやったのか。

問題概要

H*Wのマスが与えられて、各マスには0~9の数値が降られているので、適切にマスを選んで数値の和を最大化する。
ただし、各h*wの区間において、Kmin個以上選ばれている必要があり、Kmax個より多く選んではいけない。
細かいことはググってください。

最終的に提出したもの

・三点消して、適当に選べるまで選び続ける焼きなまし
・消す点はランダムに盤面からセルを選んで、 board[i][j]^2 < rand()\%100のときに消す
・追加する点は置けるセルを列挙して、重みをboard^2でつけてその中からランダムで選ぶ。選ぶたびに置けるセルを更新する
・一回の更新はO(H*W)。imosを適切に走らせたりする。Kminを満たしてるかの判定は一番最後に持って行ったりしたら速くなる。
・温度関数は temp = 4\times(1.0-{\frac{t}{T}})^2+0.01, prob = exp((now\_score-new\_score)/temp)とかいうよくわからんキモいやつ(暇だったので色々試した)
・初期状態は、一つのh*wを固定してそれを繰り返せばすべてのh*wがKmaxで埋まることを使って、その中で最もスコアが高いものを採用


 まともなスコアが出るまで方針もわからず、これビームサーチなのか?とか永遠悩んでいたけどそこそこ方針はあってたっぽい。
 消した状態を適切に評価できる気がしなかったので、消して追加するをワンセットにして焼きなましたのが個人的にはよかった。
 ちなみにこれ2倍とか高速になったら有意にスコアが上がるのでちゃんとした高速化の人がやったらもっといけていたかもしれない。
 イテレーション回数は当然入力によるんだけど大体50万~500万回ぐらいな感じ。置ける場所の列挙が遅い。
 手元で100ケース生成して、基本的にそれを頼りに最適化していた。1ケース10秒かかるし、もっとテストケース欲しかったけどこれでも時間がめっちゃかかるので渋かった。
 VPSサーバの弱いの契約してそこで走らせてたけど、多分インスタンスたくさん建ててオラしたほうがいいんだよな(安いし)。

 


 マラソン、writeupとして何を書けばいいのかわからんので、これ書けやみたいなのがあれば言ってくれれば書くかも