AtCoder Heuristic Contest 001参加記 - Brainf*ckを書かない

真面目にマラソンに取り組むのは初めてでしたが、やってみると結構楽しいですね。留年が決まって何もする気が起きず、とにかく暇だったので集中して取り組めました。留年の話は気が向いたら書きます。

先日開催されたAHC001に参加し、最終スコア989,360,207,620点、順位は32位でした。コンテスト中に考えていたこと、やったことをだいたい時系列順に書いていきます。

大事です。

入出力形式を理解できているかの確認は重要なので、簡単な解で試します。ちなみに私は、初回の提出で配列の長さが足りずにREを出しました。

入出力形式の確認ができたので、スコアを伸ばすことを考えます。

スコアが大きくなるように広告を大きくする、という操作を広告一つずつに対して行いました。

愚直解を初期解として、これを改善してスコアを伸ばしていきます。

大きな方針としては、「単純な近傍を何万回でも回して、良い近傍を引くまで待つ。無理に賢い近傍は考えない。」ということを念頭に置いていました。下手に賢い近傍を試そうとすると、実装が複雑になりがちで、大変バグりやすいので、これでもし「スコアが改善しませんでした」とでもなるとモチベに関わります。

近傍ではスコアが大きくなっていることが望ましい（はず）です。周りの広告を縮小して広告を拡大することによってスコアが改善する場合、一度スコアの悪い状態を経由しなければいけないことになります。これは嬉しくないので「縮小したら周りの広告を拡大」をワンセットで近傍とします。

スコア遷移を見てみると、ほとんど頭打ちになっているのが確認できたので、焼きなまし法に移行することにしました。 f:id:koikotya:20210325110806p:plain

人生で初めて焼きなまし法を書きました。

スコアは改善しませんでした（悲しいね）。とりあえず近傍を大きくすることにしました。

これはかなり効きました。スコアが低い広告ほど優先的に、また温度が高いときにこの近傍を取りやすいように設定しました。

近傍その2とほとんど同じですが、494億点台に安定して乗るようになったので多少の効果はあったと思います。

これ以降はアイデアが無かったのでちょこちょこパラメータ調整をして最終提出としました。

f:id:koikotya:20210325224442p:plain

焼きなまし法は試行回数が重要らしいので、高速化も多少行いました。

最大で幅 $N$ だけ拡大したいときは、 $N/2,N/4,N/8,\cdots$ というように $1/2$ ずつにしながら試します。

この高速化は結構効いた気がします。

現在の大きさから最大で幅 $N$ だけ拡大する、というように拡大するときの幅を制限しておきます。ここで、幅 $2N$ 拡大したときに重なる広告を事前に調べておきます。こうすることで、広告を拡大する時に重複判定をする広告を減らすことができます。

ただ、これはあんまり速くならなかったです。

ある広告を縮小したときに、拡大できるようになる広告は隣接していた広告（のみ？）です。事前に広告同士の隣接関係をリストにしておきます。

隣接する広告の数は一つ当たり平均で3個程度だったのでやった方がいいと思います。そこそこ速くなります。

差分だけを計算するようにしましょう。今回の問題だと比較的簡単にできて有効な高速化だと思います。

真面目にマラソンに取り組むのは初めてでしたが（2回目）、9日間飽きずに楽しめました。あまり難しい事はできませんでしたが、そこそこのスコアが出てくれたのでよかったです。最後の2日はパラメータをガチャガチャしてましたが、最初以外スコアが伸びずほとんど無駄な時間でした。

また、今回はkenkooooさんのビジュアライザに頼り切りだったので、次回からは何とかしたいですね。次回は短時間のコンテストになると思うので、効率的な分析の方法をしっかり用意しておきたいです。