AtCoder Heuristic Contest 001 - 論理とか計算機とか数学とか

https://atcoder.jp/contests/ahc001 に参加しました。

凡ミスをして暫定22位から最終77位に下がったので反省をします。

反省

こんな感じの処理を書きました。

for (int maxsize = 1000; ; ) {
  Rectangle rect = random_rect(maxsize);
  if (rect.area() > r[i] * 1.1) continue;
  // なんかを処理していい感じだったら break
  maxsize = round(maxsize * 0.8);
}

maxsize が指数的に小さくなるのでこのループは O(log(maxsizeの初期値)) 回で止まると思っていましたが、3行目で continue すると小さくなりません。r[i] が小さいときはほとんど確実に continue するのでたくさん回ります。（無限ループしてくれればローカルでテストしてる間に気付きますが、たちの悪いことに数秒かけてループを抜けたりします）

こう書くべきです。

for (int maxsize = 1000; ; ) {
  Rectangle rect = random_rect(maxsize);
  if (rect.area() <= r[i] * 1.1) {
    // なんかを処理していい感じだったら break
  }
  maxsize = round(maxsize * 0.8);
}

このバグが原因でシステムテストでTLEを8つ出しました。残念ですね。

これは main の最後に以下のような処理を書いておけば気付けた可能性があります。

if (timer.get_elapsed_time() > timelimit)
    cerr << "TIME LIMIT EXCEEDED; elapsed " << timer.get_elapsed_time() << endl;

ローカルで用意したテストケースの中にバグが露呈するケースが含まれていなければ見逃す可能性はありますが、今回は TLE の数が 8/1000 で、手元で 151 個回していました。自動的にチェックして警告を出す仕組みを用意していれば気付いた可能性はそこそこ高いでしょう。

やったこと

ついでに考えたこととか書きます。

問題を見た直後に書いたと思われるメモはこうなってた。

n がそんなに大きくなくて、盤面はわりと大きいので、衝突判定はとりあえず全組み合わせ試してもそんなに悪くはならなそう。
最初は焼き鈍しかと思ったけど、縦長の長方形が実は横長にしたほうがよかったときに横長に修正できるような近傍はあまり自明ではない。
長方形を一つ選んで、そのサイズを極端に小さくして作り直す、とか？
一時的にオーバーラップを許容する評価関数にして焼き鈍しとかはありうる？

そんなに外してはいないと思うけど、ここから掘り下げ切れなかった感がある。

あとは一つの長方形のサイズを変えるとか隣接する二つの長方形で押し合ってみるとか、その程度の局所的な変更ではたいして改善しないだろうと思ってほとんど検討しなかったけど、他の人の方針を見ていると必ずしもそうではないようだ。この辺は直感を信じすぎないで、実装して確認すればよかったのかもしれない。

貪欲法

1x1 の長方形*1を (x[i], y[i]) に作って、それらを上下左右に広げる。

広げる方向は最初はランダムにしていたが、後で複数回実行するようになったのでどの長方形はどちらに広げるとよさそうという優先度の学習っぽいことをしてその優先度に比例する確率で方向を選択した。
要求された面積に対する充足率の低い順でソートした priority queue を用意して、充足率の低いものから優先的に広げるようにするとよくなる。
ぶつかった場合に、ぶつかられた方を縮めてもスコアが上がるならそうする。これは充足率 1.0, 0.8 よりも 0.9, 0.9 の方がいいのでけっこう効果がある。
サイズを 1 ずつ広げると処理時間がかかるので、最初は200ぐらいずつ広げて、広げる幅をだんだん狭めていく。

ぶつかったら相手をずらすのもやろうかと思ったけど、めんどくさそうだったので後回しにしていたら、最終的にビジュアライザを見た感じで必要ない気がしてきて実装しなかった。

このへんは主に初日に思いついたこと。優先度は初日の早い段階から考えてはいたけど実装は後半になってからやった。

焼き鈍し

スコアを改善するにはちょっとずつずらしてもあまり意味がなくて、大幅に形を変える必要がありそうだと思った。ローカルな変更でそれを実現できるかというと怪しそうだったので、充足率の少ない長方形を選んでそれをランダムな大きさに変更してみた。当然そのままだと周りとぶつかるので、周囲にある長方形を 1x1 に戻して貪欲法をやり直すことにした。

以上の操作で得られる解を近傍として、キックしかしない焼き鈍しみたいなことをした。一応スコアは上がった。

このへんが二日目にやってみたこと。

一回の試行に時間がかかるのでぜんぜん収束せず、実行時間が10倍ぐらいあるとよさそうだと思ったが、この時点では衝突判定でかなり高速化ができると思っていたので試行回数10倍ぐらいにできるつもりでいた。

高速化

衝突判定の高速化を試みた。長方形の各辺の座標がわかっていれば、右端の座標が x のものを x + a にしようと思ったら、左端の座標が [x, x + a - 1] の範囲にあるものをすべて調べればよいはずで、これで高速化できると思っていたのだが、意外とそうでもなかった。でも少しは速くなった。

これが三日目にやったこと。高速化を頑張ったけどあまり成果が出なかった日。

これ以降はわりと細かい調整ばかりしていた。

*1:正方形は長方形です