AHC001 参加記

AHC001に参加しました。
長期のコンテストにC++を使いたくなかったのでRustで参加

githubで管理してたので公開します https://github.com/kanra824/ahc001

1日目

  • (x, y)に1 * 1の正方形をおいて初期化: 823090
  • それぞれの長方形をランダムに選んで拡張する: 35830035700

  • 長方形を広げたり縮めたりしながら山登り: 44048518763

  • 50個分を非同期実行するシェルスクリプトを書いた（2並列 * 25回）

  • （脳死で50個同時に非同期実行させて回しまくってたらブルスクが起きて焦った　CPU温度が大変なことになるからやめようね）

  • ビジュアライザが出力した画像の一覧をブラウザで見れるようにした　素のJSでゴリッと

  • 公式のビジュアライザを改造して、全体のスコア(/ 109)や長方形ごとのスコア(*100) が表示されるようにした
    f:id:mdyh2a380824:20210308001844p:plain
    こんな感じ

2日目

  • 焼きなまし: 47498289869

  • 拡張する時に他の広告が重なるならその広告を縮める: 47804220369

  • テストケース生成をｼｭｯとできるスクリプトを書いた

3日目

  • 更新するidxを選択するときの確率分布をスコアに応じて決められるようにした
  • 差分更新をより高速化

その他

  • optunaで初期温度と終了温度を探索するやつをかいた（使うかな？）
  • ビジュアライザをシークバーで動かせるようにした
  • 動画: https://github.com/kanra824/ahc001/pull/15

4日目

  • 広告がずれてくれるように、縮小して拡大する遷移を追加した
  • 序盤はスコアが均一になるようにした: 48176775941
  • 今までやってきた焼きなましが時間を書けてもそんなに変わらないことに気づいたので、何度か回すことにした
  • ループを回しながら、各回の焼きなましの結果スコアが低かった広告をいくつか取り出して、次のループではそれらの広告が最初に拡大されるようにした: 48453049603

5日目

進捗0

6日目

  • 広告の変化しにくさみたいなパラメータを入れる
  • 長方形の辺と辺がぶつかったとき、たまにいい感じに縦横を入れ替える
  • めちゃくちゃバグっています　HELP
  • なおった
  • スコアが....スコアが伸びない.....

7日目

  • 色々試したけど伸びなくて、結局4日目のやつを提出

感想

490にのせたかったけど、結局485にも乗らなかった... Rustはとても良くて、リファクタリングをするときに威力を発揮してくれたと思う。 C++でやってたら途中で管理しきれなくなっていた