ICFPC 2019

2019-07-01

ICFP Programming Contest 2019 に一人チームで参加した。 順位表フリーズ時点 (終了3時間前) で14位だった。フリーズ時点からほとんど点数が上がってないのでもう少し低い順位だと思う。

repository の履歴を見ながら、やったことをメモしておく。

1日目

  • 19:00 - 問題文が公開される
  • 20:30 - すべてのインプットに対して問題を解く shell script を作る。 並列化しようと GNU parallel の使い方を調べ始めて1時間ぐらい溶かしたが、結局使うのは諦めた。
  • 23:10 - とりあえず動くAIを書いた。manipulatorを無視して、一番近い塗ってないマスに貪欲に移動する。この時点で2位になったがこれ以降下がるのみ。
  • 24:10 - スコア計算機を書く。相対評価なので、ベストスコアはフィールドの面積から適当に決めた。

shell script を増やしたり、家のCPUの6コア全部使うためにテストケース並列化したり、多点スタートにしてみたりして終わり。

2日目

  • 7:30 - 起きたら問題が増えている。
  • 10:30, 10:45 - main.rs にべた書きしてたのをリファクタリング。
  • 11:00 - また問題が増える。
  • 11:45 - manipulator の通る部分を考慮するようにする。
  • 12:45 - manipulator を増やす booster を使うようにする。実装が悪くて100000個のenumの配列を何回も初期化してたので、enumに新しいフィールドが増えた途端実行時間が10倍ぐらいになったので最適化した。
  • 13:30 - fast wheel を使ってみる。点数上がらないのでもとに戻す
  • 14:45 - 実行時間が遅くなってきたのでいい感じのプログレスバーをつける。
  • 15:15 - 近くにboosterがあったら拾う。
  • 16:15 - ドリルを使ってみる。点数が上がらないのでもとに戻す
  • 16:45 - テレポートを使ってみる。点数が上がらないのでもとに戻す
  • 18:30 - ビームサーチを実装してみる。実行時間が遅すぎるのでもとに戻す
  • 19:00 - 最初の24時間が終わり。マイニング要素が追加される。
  • 22:00 - マイニング用の関数をRustから呼び出せるようにする。

分身を実装してたら眠くなったので2日目は終わり。

3日目

朝からマイニング用のソルバーを書く。

  • 15:00 - それっぽいマイニング用のパズルソルバーができる。
  • 16:30 - マイニングが動き始める。
  • 18:30, 18:45 - 分身を実装してみる。点数が結構増える。
  • 19:45 - manipulator が強いので積極的に取る。
  • 21:45 - マイニングの結果が気になるので、各回の獲得金額を表示させるプログラムを書く。
  • 22:00, 22:45 - 次の開いてるマスを選ぶ方法の最適化。同じ距離でたくさん同時に塗れるならそっちを選ぶ。

4日目

  • 08:00 - 回転を実装する。点数がまあまあ増える。
  • 09:30 - これまで実行してきた結果のうちbestなものを選んで提出するようにする。点数がまあまあ増える。
  • 12:45, 13:15 - マイニングしたお金で分身を買うようにする。買うステージは大きいものから順番に買えるだけ買う。
  • 13:30 - EC2 で 72コアマシンを借りてひたすらランダムで回し続けていい乱数を引くのを待つ。10連ガチャ1回分くらいのお金を失う。
  • 14:00-16:00 - バグを潰したり細かい改善を試したりする。
  • 16:00-19:00 - 3時間で実装できそうな改善のアイデアがないので計算を回すぐらいしかやることがない。