blog2019-01-31MM107参加記マラソンマッチにおそらく初めて最初から最後までちゃんと取り組んだら実力に見合わない結果が出たので何をやったのかの記録standings多くの人は別のこともしながらMMをしているはずなので、ずっとMMをしていた僕が有利なのはそれはそうなのだけど、それでもうれしいっちゃ嬉しい。てわけで何をやったのか。問題概要H*Wのマスが与えられて、各マスには0~9の数値が降られているので、適切にマスを選んで数値の和を最大化する。各h*wの区間において、Kmin個以上選ばれている必要があり、Kmax個より多く選んではいけない。細かいことはググってください。ときに消す・追加する点は置けるセルを列挙して、重みをboard^2でつけてその中からランダムで選ぶ。選ぶたびに置けるセルを更新する・一回の更新はO(H*W)。imosを適切に走らせたりする。Kminを満たしてるかの判定は一番最後に持って行ったりしたら速くなる。いうよくわからんキモいやつ(暇だったので色々試した)・初期状態は、一つのh*wを固定してそれを繰り返せばすべてのh*wがKmaxで埋まることを使って、その中で最もスコアが高いものを採用まともなスコアが出るまで方針もわからず、これビームサーチなのか?とか永遠悩んでいたけどそこそこ方針はあってたっぽい。消した状態を適切に評価できる気がしなかったので、消して追加するをワンセットにして焼きなましたのが個人的にはよかった。ちなみにこれ2倍とか高速になったら有意にスコアが上がるのでちゃんとした高速化の人がやったらもっといけていたかもしれない。イテレーション回数は当然入力によるんだけど大体50万~500万回ぐらいな感じ。置ける場所の列挙が遅い。手元で100ケース生成して、基本的にそれを頼りに最適化していた。1ケース10秒かかるし、もっとテストケース欲しかったけどこれでも時間がめっちゃかかるので渋かった。VPSサーバの弱いの契約してそこで走らせてたけど、多分インスタンスたくさん建ててオラしたほうがいいんだよな(安いし)。検索はてなブログをはじめよう!gasinさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。