AHC001 参戦記録 p.41
itsukiです。
AtCoder Heuristic Contest 001 に参戦した様子です。解説記事ではありません。
ヒューリスティックコンテスト（マラソン型コンテスト）に初めて参加しました。2021-03-06(土) 12:00 ~ 2021-03-14(日) 20:00 の間、自分が思いつく限りを試せたので満足です。
「Rust 言語で書かれたツール（入力ジェネレータ等）を提供します。」とのことだったので、当初は Rust 環境を整備したりしましたが、kenkoooo さんが公開してくださったツールを利用させていただきました。ありがとうございます。Rust で Hello world! した件については、いずれ note に書こうと思います。
プレテスト最終結果：44,480,088,997 点
以降、この記事に書かれている点数はすべてプレテストの点数です。
方針1. 1×1（823,090点）
思いつく方法をあれこれ試したくなるが、とりあえず正の得点を取る
すべての広告の面積が 1×1 になるようにすれば、他の広告とも被らない
方針2. 横縞①（4,246,856,211点）
すべての広告について、縦の辺の長さを 1, 横の辺の長さを 10000 に設定
方針3. 横縞②（42,952,437,235点）
方針2 に加えて、要求面積を超えない かつ 隣接する広告と接するまで、縦の辺の長さを 1 ずつ増やす
”i ≠ j のとき ( x_i, y_i ) ≠ ( x_j, y_j )" とのことだったが、念のため x 座標だけ被ったり y 座標だけ被ったりした場合を考慮して、重複数に応じて縦縞や横縞に変化するようにした（つもりだったが、当時のソースを見るとそうならない気がする…）
方針4. 上下左右可能な限り拡大（44,010,538,961点）
要求面積の小さい順に（なぜそうしたのかは忘れた）、上下左右すべての方向について、広告設置スペース端 もしくは 隣の広告に接するまでの距離を調べる
最も余裕のある方向へ、要求面積を超えない程度に、できる限り面積を広げる処理を繰り返す
表示してみたところ、方針3 のような縞模様になって笑った
方針5. 四隅から順に拡大（44,480,088,997点）
広告設置スペースの四隅、点 (0, 0)、点 (0, 10000)、点 (10000, 10000)、点 (10000, 0) それぞれについて、一番近い ( x_i, y_i ) を持つ広告を探す
まず 点 (0, 0) に一番近い広告について、上 -> 左 -> 下 -> 右 の順に、要求面積を超えない程度に、できる限り面積を広げる
次に 点 (0, 10000) に一番近い広告について、左 -> 下 -> 右 -> 上 の順に、同じように面積を広げる
次に 点 (10000, 10000) に一番近い広告について、下 -> 右 -> 上 -> 左 の順に、同じように面積を広げる
最後に 点 (10000, 0) に一番近い広告について、右 -> 上 -> 左 -> 下 の順に、同じように面積を広げる
という処理を全広告に対して順番に行う
上下左右の処理順序は、単にバラバラにしたかっただけで深く考えていない
まとめ
・「焼きなまし法」「山登り法」を履修すること
・次回は、実行制限時間をギリギリまで使って愚直に試すこと
・次回は、もっと多くのテストケースを手元で回すために試行錯誤すること
感想
アルゴリズムも何もなくごり押ししてしまいましたが、参加前に想像していたよりも高得点が取れて嬉しいです。改良したつもりが改悪だったり、全然違う方法を試したつもりが似たような結果になったりしましたが、毎日あれこれ考えながらじっくり試せて楽しかったです。
コンテスト後、上位の方々の解説で「適当な確率」や「ランダム」という言葉が出てきて、そんな方法があるのかと驚きました。勉強になります。解説記事を書いてくださっている皆さん、本当にありがとうございます。
今後、AHC001 のような 1週間強のコンテストと、1日未満のコンテストが、交互に約1か月間隔で開催されるようなので、また参加したいと思います。
8日と8時間でしょうか、お疲れさまでした。寝食を忘れてすっかり没頭してしまいました。完全に寝不足です。遊び尽くせたので大変満足しています。ありがとうございました。
引き続き、のんびり精進します。
追記
のんびり下書きしている間にシステスが終わり、最終結果が出ました。
順位：663 / 1505 位
得点：888,155,692,608 点
パフォーマンス：1280
レーティング β：0 -> 297 (+297)
パフォーマンスが見たことない桁数になりました。嬉しい。
この記事が気に入ったらサポートをしてみませんか？