問題
https://www.icfpcontest.com/specification_v3.pdf
M人のミュージシャンと A人の観客がいて、観客の満足度を最大化する問題でした。
満足度はミュージシャンと観客の距離とミュージシャンが演奏する楽器の種類によって決定されます。また、ミュージシャンと観客の間に別のミュージシャンが別のミュージシャンが一定範囲内に存在する場合は「他のミュージシャンの演奏によって音をブロックされた」と判断されスコアの計算から除外されます。
あとは、同じ楽器を演奏するミュージシャンの距離によってボーナスポイントが増えたりとか、演奏のボリュームによってスコアが増減したりとかありますがそのあたりは元の問題を参照してください。
方針
ミュージシャンの位置を変化させる焼きなまし、近傍としては次の 3つです
- ミュージシャンをステージのランダムな位置に移動させる
- ミュージシャンを現在の位置から少しだけ移動させる
- ミュージシャン 2人を選び位置を交換する
変更後はスコアの差分計算を行いますが、自分の計算量は O(MA) だったのに対して上位の人達を見る感じあともっとオーダーを減らせたみたいです。（多分千倍ぐらい違うのかな）
順位としてはフリーズ時の時点で 14位でした。
感想
初めて参加してみたのですが、思ったより普通のヒューリスティックの問題が出たなという印象でした。（毎年 twitter のタイムラインに流れてくる情報だけだと変わった問題が多い印象だったので）
焼きなましの問題だとまずスコアの差分計算を高速化しないことには勝負の土俵にも立てないので全然ダメでしたね。（マシンパワーを持ってしても数百倍近くを覆すのはまぁ無理）
せっかくチームOK なのでチームで出ても良かったなと思いました。（ただ、自分の熱量として「うおおお絶対勝つぞ！！！」みたいな感じでもないのでメンバーに迷惑をかけそうという不安はある）
雑なまとめ
序盤、API 経由でサブミットしたときにずっと「Processing」状態で何が悪いのかわからなかったのがかなり面倒だった（結局は提出時の JSON の形式が問題だった）
絶対スコアが順位が決まるけど、問題ごとの点数のブレが大きくて (100倍ぐらい違う）寄与率が高いケースに強い人がそのまま勝ちそうだなという印象。
discord にアナウンスが流れてきてるけど英語読むの面倒だな。
3日目、キーボードを触り続けてたせいか小指を痛めた。
コンテスト開始から 24h ごとに追加の仕様が発表されるけど最初から全部表示じゃダメなんかな。この仕様だと最終日にちゃんと参加出来るかどうかが順位にかなり影響しそう。
1個目の追加はまぁまぁ影響あったけど 2個目の追加はよくわからなかった（スコアが定数倍伸びただけでは）
無制限に実行出来たけど、ずっとマシンリソース取られるのも嫌だったので最長でも 20分とかしか回していない（一応前回の実行結果を次の初期値にしてたので実質 20分以上は回してはいた）
