AHC001 参加記
こんにちは、ゆうです。この度はAtCoderの記念すべき初Ratedヒューリスティックコンテスト、AHC001に参加したので、何をやったか、何をやらなかったかを整理して、今後のAHCに向けてもっと強くなりたい、という気持ちから参加記を書いてます。
結果から言いますと、
執筆時点で最終的なシステムテストが始まってないのですが、サンプルでは57位でした。個人的には十分に満足のいく順位なのですが、長期コンテストで時間をかなりつぎ込んだ結果なので、もっと素早くこの順位になれるようにしたいです。
やったこと、やってみたけど改善につながらなかったこと、やりたかったことの順で書いていきたいと思います。
何をやったか（時系列順）：
初期：
- それぞれの広告にとって必要な点を1ピクセルずつ与え、それぞれぶつからないように広げる。431億点＝86％程度
- 直感的に、箱詰めをするときに箱を振るともっとたくさんの物が入るなぁと思い、時間いっぱいまで、振る*1、広げる、を繰り返す。449億点
- 広げるときにぶつかったらやめるのではなく、一つの広告だけが邪魔で、押し返したほうが得するときは押し返す。480億点
- 広げる順番をランダムに変えていく。481億点
中盤：
- 押し返すときに、一つの広告だけではなく複数押し返せるように書きなおし。48５億点
- 定数倍高速化のために1ずつ伸ばすのではなく、先に100伸ばせるか確認、次に10伸ばせるか確認、最後に1伸ばせるか確認、をする。広げるときに一定確率で、縦に広げたがるモードや横に広げたがるモードに突入するようにする。486億点
- 定数倍高速化のために、一番最初に各点ごとにどの点が左右上下にあるかを保存し、例えば上方向に広げるときは上にある広告だけ確認する。487億
- スコアが低い広告をランダムに数個選び、リセットし、広げ直してみて、改善するか山登り。487.9億
- スコアが低い広告を選ぶのと、隣り合わせでぶつかってる広告ペアを選ぶのを交互にやる。490億
- 隣り合わせのやつだけにして、広げる順番を工夫する（もっと広がりたがってた広告を先に広げる）。491億
終盤：
- 山登り法を焼きなまし法に変える。491.9億
- 焼きなまし法のパラメータガチャ＋100，10，1伸ばせるか確認していたのをbase^2,base,1に変更して、baseをランダムに決定していく。492.7億
- 最後に一回広げるときに、得する場合指定サイズを超過することを許す。最高点493.3億達成だけど、これは上振れで再提出してみると492.7のまま。
- 押し返すだけではなく、つっかえて邪魔になっているものを時々そのまま別の広告に渡す。平均493.0 最終提出
やってみたけど改善につながらなかったこと
- 衝突判定でほぼ全部の広告をいちいちなめているのが時間がかかっているので、各ｘ、y値でどの広告の辺がそこにあるかを持つことによってO(logN)にする。実装してみたものの思いっきりスピードダウン。setの定数倍が。。。
- 衝突判定で、例えばすでに右辺がｘ＝5000である場合、200より右にある広告だけ確認するために、先に広告を順列にしておいて、5000より右はどこから見ればいいかを各x、yごとに保存する。 バグでWA。かなりデバグに時間を費やしたものの原因がわからずあきらめる。
- 低い点数の広告の周りを重点的にリセットする。「低い点数」は動的に定義（最小スコアの広告と1の中間値より下、とか）なぜかスコア減少。原因がわからず。
やりたかったこと
- 一つの広告が複数を押し返すのはやったんだけど、逆に一つの広告が複数の邪魔になっている（複数の広告の利益を足すと損失より大きいけど、各広告ごとには損失の方が大きい時）、押し返せるようにすること。初期からずっとやるつもりだったけど、実装が爆発しそうで断念。
- 押し返すだけではなく、つっかえて邪魔になっているものを時々そのまま別の広告に渡す。最終的に少しやったけど、たまたま伸びの大きさが十分な時だけになっていて、つっかえた後を貪欲に確認するものを書きたかったが、実装爆発＋時間切れ。
個人的な感想、反省
反省点としては、環境構築をサボった結果、100行程度しか出力できなくて、さらにAHC中はつまりがちだったAtCoderのコードテスト機能に頼りっぱなしだったことです。手元だと実行速度が違いすぎて無理だったので、AtCoderに近い実行環境を次回までに探しておきたいです。また、普段*2よりはちゃんとやったのですが、関数などを使い分けることにより、デバグをしやすくしないといけないと痛感しました*3。あと、普段よりいっそう定数倍の遅さが気になるコンテスト形式なので、言語をもうちょっとどうにかできないか、考えものでした。*4
Ratedということで今までのヒューリスティックコンテストよりたくさんの方々が参加して、すごく楽しかったです。特にツイッターでのライバルの方々とバトルしたり、長期コンテストだからこそ楽しめる駆け引き*5もありました。これからもバシバシ参加していきたい所存です。
