参加してました。
https://hokudai-hitachi2017-1.contest.atcoder.jp/
やったこと
とりあえず submit (52935)
左上から丁寧に並べる
焼きなましする (52935 -> 149624)
近傍は ランダムな2点の位置を交換する
温度管理を調整 (149624 -> 155183)
雑に設定していたパラメータをちょっと調整
遷移させるかどうかの閾値を設ける (155183 -> 156319)
確率的に遷移させるけど、あまりにもスコアが下がっていたら遷移を却下する。
近傍を変える (156319 -> 159568)
ランダムな2点の位置を交換する
から ランダムな辺を選び終点の周辺マスを1つ選択する。既に点がある場合は交換、ない場合はそこに点を移動させる
に変更。
これだと、必ずスコアに影響がある近傍になるので効率が良い。
初期解を変える (159568 -> 160152)
最初から中央に配置しておくことで移動のバリエーションが増える (気がする)
諸々高速化 (160152 -> 160950)
盤外判定を削除したりとか
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
高速化 (160950 -> 161572)
辺の重みを int
で管理してたのを char
にしたら速くなった
細かく確認してないけど、この時点での試行回数は 2億5千万前後ぐらいだったと思う。(3億は目指したかった)
パラメータ調整 (161572 -> 163024)
ひたすらパラメータ調整。(このときはまだ、システムテストとか無かったから適当に submit しながら調整してた)
辺の一部のみを採用する (163024 -> 163653)
全部の辺を使ってたけど、各頂点から生えている辺を重さ順で並べて、その上位だけを使用するようにした。