鉄則本マラソンの解法(ネタバレ注意)
最高得点の提出(94,787,901点): https://atcoder.jp/contests/tessoku-book/submissions/35706008
各特別区に割り当てる地区を焼きなまし法で決める解法。
・初期解の作成
まず、各特別区について、最初の地区を盤面中央の25x25マス内にあるものの中からランダムに選択する。次に、まだどこにも割り当てられていない地区に隣接している特別区の中から、人口が最小もしくは役所職員数が最小のもの(どちらにするかはランダム)を1つ選択し、隣接する割り当てられていない地区のうちランダムな1つをその特別区に割り当てる。これを全ての地区が特別区に割り当てられるまで繰り返す。
・焼きなまし
近傍は以下の2種類とした。
- ある1つの地区に割り当てる特別区を、隣接する別の特別区に変更する。
- ある1つの地区と、他の特別区に割り当てられた他のある1つの地区について、地区同士の所属する特別区を交換する。
・反省点
関節点に相当する地区によって特別区の拡大・縮小が不可能になり、点数がある一定の点数から伸びなくなる問題があったため、それを初期解を工夫することで解決しようとしたが、完全には上手くいかなかった。
ある特別区に属する地区を複数個別の特別区に割り当てる近傍を用意する解決策も考えていたので、そちらも試してみるべきだったかもしれない(実装コストが重そうだったことと、焼きなましの試行回数が大きく減少して不利になるだろうと判断して、今回はこの方針を捨ててしまった)