CADDi 2019に参加しました
AtCoderで開催された、キャディ株式会社主催のマラソン系コンテストCADDi 2019に参加しました。
結果は16位入賞で結構嬉しいです。
コンテスト中の8時間と、前後のアレコレを書いておきます。
コンテスト前
8時間コンの走り方が分からないので、良さげな解説を探す。
qiita.com
↑の記事が過去の8時間コンを題材に解説していて大変参考になる。
僕の理解で噛み砕くと、
- 初期解を作る
- ランダムに解を動かして少しずつスコアを上げていく（山登り法）
- 余裕があれば、局所解を避けるためにスコア低下を条件下で許容する（焼きなまし法）
という感じでしょうか。
とりあえず1を達成して軌道に乗せ，2を頑張る感じで走ることにしました。
（3は力量的に手を出さない。）
以下コンテスト中経過（時間は適当）
13:00(0時間経過)
問題を読む。
- 箱の中に球を配置して、各球に割り振られた点数を得る。
- また、指定された球のペアが指定された距離より近い場合はボーナス点数を得る。
- 球は1000個、ボーナスは100000ペア、実行時間は3秒。
サンプルコードが公開されている。そのまま提出。
8,094,745点
サンプルインプットも公開されていたので、ジャッジコードを書き始める。
14:00(1時間経過)
ジャッジコードができる。
ジャッジの採点部分を流用してsolverを書き始める。
15:00(2時間経過)
最初のsolverが出来る。
点数の生成パートを読まなかったので「どうせ大きいのを詰め込めばいいんでしょ」という気持ちで書いた。
63,487,240点
これを初期解として、配置した球をランダムな方向に動かす山登りを実装したが、思うようにスコアが伸びない。
デバッグのために、イテレーション毎のスコアの変化を見てみる。
どうも当たり判定に時間がかかりすぎて、時間内に十分な回数のイテレーションを行えていないようだ。
当たり判定に時間がかかるなら、当たり判定を行わなくても良い移動を行えば良いのでは？という思いで、
- 同じ大きさの球の位置をランダムに入れ替える
- スコアが下がったら元に戻す
という更新で山登り法を実装した。
69,591,063点
16:00(3時間経過)
球の入れ替え操作は、箱の中に球が多いほど候補が増える？
初期解作成パートでは大きい球より小さい球を優先すべきなのでは？という気持ちになる。
初期解作成パートを
にした。
81,678,888点
小さい球を使った方がいいみたい？
調べてみると、現状で箱の中の球の数は200ほどと少ない。
初期解作成パートをもう少し真面目に考えるかという気持ちになる。
- 大きい球からランダムに箱に配置していく。
- 10000回くらい試しても入らないなら、箱の中の最大の球と交換する。
球が500個近く箱に収まるようになった。
149,602,369点
17:00(4時間経過)
初期解が良くなったので、swapの操作を加える。
255,387,836点
操作の度に全ての球について採点を行なっているのが無駄なので、変化のあった球だけ採点を行うようにする。
高速になってイテレーションが増えるはず。
288,156,802点
18:00(5時間経過)
同じ大きさの球だけでなく、時々大きさが1違う球ともswapするようにする。
333,608,151点
晩御飯タイム。
19:00(6時間経過)
同じ大きさのswap、大きさの異なる球のswapに続いて、球を少し動かす操作も加える。
363,449,670点
20:00(7時間経過)
万策尽き、パラメータいじりくらいしかできなくなった。
ここが実力や体力の限界か...。
374,441,154点
21:00(8時間経過)
コンテスト終了。
16位やんけ！嬉しい。
めっちゃ疲れた。
22:00(9時間経過)
AGC032(110分)が始まったので参加。
後日談
コンパイラをGCCからClangに変えたら点数が上がった。
感想
- 8時間コン苦しいけど楽しかった。
- 初期解を作って改善させていくフローに乗れたのがよかった？
- 強い人の感想ツイートを読むと、とても賢くてビビる。
- 問題生成パートはしっかり読むべきだったかも。
- CADDiさんありがとうございます。
