マラソンマッチ初挑戦でした。結果は案の定6/6位でした。
問題の概要は次の通り
- 辺の長さの決まっていないグラフが与えられる。頂点を700*700の平面上の整数座標の任意の点に配置し、辺の交差の数を減らせ
- 頂点の数 10 <= V <= 100
- 辺の数 2*V <= E <= 5*V-1
- 頂点の位置はダブってはならない。
- それぞれのテストケースにおいて、交差の数が自分のスコアとなる。他の人と勝負して、その人よりスコアが少なかったら（交差が少なかったら）自分に1ポイント、引き分けなら0.5ポイントあたえられ、そのポイントによって順位が決められる。
- 実行時間制限は10秒で、メモリは1024MBまで
- 無効な値を返したときは、テストケースは0ポイントで部分点はなし
- ビジュアライザー公開されているので、自由に利用できる。ソースコードの評価関数を流用することも可能
時系列
9:45 ごろ
マラソン開始 問題を読み始める。
redmineのwikiを使って、問題文の翻訳をしていく
10:15 ごろ
問題文を読み終わる。とりあえずランダム解を提出してみると、20ポイントになった。
ビジュアライザーのソースを読み始める
12:15ごろ
ビジュアライザーのソースの重要なところを読み終わる。
ビジュアライザーで遊んだりする。
とりあえず、ソースから流用して、同じ答えを返す評価関数を作り始める
13:30ごろ
点や辺の実装はポインタを利用したほうが楽だということに気づくが、後の祭りなのでそのまま書き続ける。
14:30ごろ
評価関数を含めて、必要なユーティリティ関数がほとんど完成する
15:30ごろ
とりあえずモンテカルロ法で書いたソースを提出してみる。あまり点数が上がらない…
15:35ごろ
交差を少なくすることが目的のはずが、交差の多いものを優先的に選ぶようなコードを書いていた。絶望。とりあえず、山登り法に改造する
17:00ごろ
あまり点数が上がらない…
18:00ごろ
時間がたつにつれて、探索範囲を狭めるようにしてやると、劇的に交差の数が減ってテンションがあがる。
19:30ごろ
交差判定の評価関数が重そうな気がしてきたので、改造するが、答えが微妙に合わない（←別に厳密じゃなくても良いということに気づいてなかった。）しかたがないので、正確に動作するものを使い続けることにする
20:00ごろ
焼きなまし法に変更してみるが、思ったほど成績が芳しくない…
山登り法のパラメータ調整を始める
21:15ごろ
だいたい満足いくコードが書けたので、提出する。
22:00
マラソン終了
結果は6/6位。
22:30
特定のテストケースで無限ループに陥ってしまい、
TLEして点数が0になっていることが判明。
また、実行から9.3秒で探索を打ち切ることにしていたが、微妙に間に合っていないことが判明。
23:00
そのあたりを修正すると、劇的に点数が上がって絶望
反省点
- Test!! Test!! Test!!!
- 時間とともに探索範囲を絞り込むのに使うパラメータは、最適化の回数ではなく、時間をもとに計測するべきだった
- 時間いっぱい山登り法を行う前に、ランダムに配置を行なっていたが、その配置を工夫したり、山登り法の途中で配置を入れ替えたりするなど（遺伝的アルゴリズムでいう「突然変異」）、局所解に陥らない工夫を取り入れれば良かった
- パラメータ調節を手動で行なっていたので、自動化するべきだった
- 交差判定に使う関数は、少しくらい間違っていても良いので、高速なものをつくるべきだった
- プロファイラの使い方を勉強しておいたほうが、何かと便利
