2021/3/6-2021/3/14に開催されたAtCoder Heuristic Contest 001に参加しました。
普段は、いわゆるマラソン系のコンテストに参加することはありませんでしたが、今回は記念すべきAtCoderヒューリスティック系の第1回目という理由のみで、参加をすることにしました。
ちなみに、私がAtCoderを初めたての頃、ヒューリスティックコンテストの入門編コンテストが開催されて参加はしたのですが、結局0点で終了という残念な結果しか残せませんでした。
よって、今回は少なくともまともに得点を取るという、めっちゃ低いハードルを設定してコンテストに臨こととしました。
AtCoder Heuristic Contest 001 - AtCoder https://t.co/Rsho0lahks
— devgenjin77 (@devgenjin77) 2021年3月6日
ゆるりと参加します。目標はちゃんと得点をとることw
今回の結果
で、今回の結果ですが、なんとかそれなりの点数をとることができました。
パフォーマンスは、1,356。これが良い方なのかどうかはよくわかりませんw
振り返り
とりあえず提出だけはした、という感じです。
A問題
の正方形上に、企業の広告スペースを適切に配置する問題。
各企業の希望位置
と希望サイズ
が与えられるので、希望位置を含み且つ希望サイズに近いスペースを確保し、各企業の満足度の総和を最大化するということすが、まずこの手の問題に取り組むのが全く初めてなもので、どういう方針で行けば良いのかがよくわかりません。
ということで、最初の土日は前回のヒューリスティックコンテストの解説を読みながらいろいろ方針を考えつつ、夜はABCやARCがあったので、とりあえずそちらに専念することにしました。
で、平日はというと、なかなか仕事が忙しくて時間が取れなかったのでコンテストの方は進捗ゼロ。
結局、13日土曜になって、このままだとノー提出でフィニッシュになりかねんということで、やっとこさ重い腰を上げて実装に取り組むことに。
で、まず実装方針を立てるにあたり、以下のような考察をしました。
- 希望位置が含まれない企業については得点ゼロになるので、希望位置が密集している状態でも、ある企業を希望位置からどかすようなことはしない方が良いかも。
- 広告スペースについては、希望サイズから大きすぎても小さすぎても行けないので、なるべく希望サイズに近づけるようにする。
ということで、最初は、各企業の広告スペースを希望位置を含むサイズのスペースを配置。あとはランダムに企業を選び、希望サイズに満たない場合は、
のランダムな範囲で上下左右のランダムな方向いずれかにスペースを引きのばし、他の企業と被らない且つスコアが上がる状態であればそれを採用するという実装をすることにしました。
とはいえ、こんな一見単純な実装も実際にやってみるとなかなか骨が折れる。最初は重複チェックのとこがバグってたりして、まともな得点がとれるプログラムになるまで、大分苦労しました。
結局、最初の実装が完成したのが13日のABCコンテストに参加した後。なんとか最終日のギリギリでまともなスコアが出るプログラムが完成しました。これでとりあえず1回目の提出。
その後、一度に増やすスペースの幅を調整したりなんかして、少しスコアが改善したようなので、14日の16時にもう一回提出しました。
Submission #20922652 - AtCoder Heuristic Contest 001
で、これが最終の提出で作った、サンプル入力に対する出力結果です。
自分で作ってた当初は、まーそれなりに上手くできてるやんと思ってました。
しかし、上位陣の作った結果をみてると、空白部分がほとんどないものばかりで、自分が作ったのがまだまだ足りない部分が多いなーというのが正直な感想です。
今回の上位陣は、焼きなまし法などを使い最適化のための工夫をしているのに対して、こちらはランダムに広げるだけという単調なプログラムになっており、その差は歴然としていました。
総括
今回、初めてまともにヒューリスティック系のコンテストに参加し、なんとか提出までこぎつけましたが最適化のための工夫が全くできておらずでした。次回のAHCが開催されるまでには、少なくとも焼きなまし法の実装方法は勉強しておこうと思います。
また、次回も頑張ります。
