AHC039 参加記
概要
2024-11-11(日)に開催されていたプログラミングコンテストである、THIRD プログラミングコンテスト2024（AtCoder Heuristic Contest 039) に参加しました。
今回は、二次元累積和を使った解法で、751人中221位を取ることができました。ABCでよく使っていた累積和をAHCにも使えて楽しかった！というのもあり、参加記を書いてみました。
どなたか一人でも参考になる方がいれば幸いです。
問題文
二次元平面上にサバ(+1点)とイワシ(-1点)が5000匹ずつ分布しています。
多角形の網(いくつか条件有り)を張り、網の内部の点数を最大化しましょう。
try1: とりあえず通す
まずはとりあえず通すため、(0, 0), (0, 100000), (100000, 100000), (100000, 0)を出力するだけのコードを書きました。
seed 0のビジュアライザです。もう見た
try2: グリッドに分割して、適切な長方形を選ぶ
今回のAHC039は短期コンテスト(4時間)のため、(今の自分の実力では、)実装が重いアルゴリズムを使うとバグらせて提出が間に合わなくなる可能性があります。
初めは「クラスタリング」や「点群」や「凸包」といった単語をWebで調べていましたが、途中で、網の形を複雑にするのは現実的ではないと判断しました。
そこで、 「網は長方形に限定する」 という制約を付けました。これなら、以下のアルゴリズムで確定的に最大スコアの網を選択できます。
- 盤面をM×Mのグリッドに分割する。
- M×Mの二次元累積和を計算する。
- 網の左上の頂点の座標と右下の頂点の座標をM×Mのグリッド内で全探索し、スコアが最大となる網を探す。
- 実際の座標に戻して出力する。
手順3がO(M^4)になるため、Mは100～150あたりが適切でしょう。
提出したところ、291,267点になりました。
seed 0ではこのような感じです。seed 0単体のスコアは1547でした。
try3: 長方形の四隅を削る
まだ時間があったため、try2からの微改善案を考えました。
長方形の四隅にスコアが負の領域があれば、それを削ることでさらにスコア向上が目指せそうです。これなら、実装もそこまで重くはないでしょう。
。。。
。。。バグらせました。
あーあーあーあー
最終結果
残念ながらコンテスト中にtry3を通すことはできず、最終結果はtry2のままとなりました。
それでも順位は751人中221位となり、過去最高の順位を取ることができました！
レーティングも上がり、AHCでも緑になりました。とても嬉しいです。
おまけ1：try3延長戦
本番でtry3をバグらせたのは、累積和用のグリッド座標と実座標の変換をしっかり考えていなかったためでした。
例えばM = 100でグリッド幅が1000の場合、グリッド左上の座標は(1000m, 1000m)で、右下の座標は(1000m + 999, 1000m + 999)である (1001mではない) 、というような。
境界がどちらに属するかにはきちんと注意しないといけませんね。。。
直したところ、316,906 点で延長戦163位につけることができました。
seed = 0でのスコアは1657点 (try2から+110点) でした。
おまけ2：乱択
Twitterで「乱択」という言葉が多く上がっていました。
今回は累積和を使いましたが、そもそも確定的に最善の領域を探す必要が無いのですね。。。AHCならではの気づきでした。
こういう形のようです。次のAHC040で使えそうなら使ってみたいです。
int solve () {
int TIME_LIMIT = 1.0 * CLOCKS_PER_SEC; //問題の制限時間を見て変える
int startTime = clock();
while (clock() - startTime < TIME_LIMIT) {
ランダムに長方形を選ぶ()
内部のスコアを計算する()
スコアが最大を更新したら、記録する()
}
}
おまけ3：複数領域を包含する輪郭の実装
Twitterを眺めていたところ、今回のtry2で実装が重いと判断して諦めた、「複数領域をすべて包含する輪郭を作る」方針で実装をやり遂げられていた方がいました。
とても参考になったのでリンクを貼らせていただきます。
これをコンテスト中に実装できるようになりてえなあ。
終わりに
ABCでも良く出てくる累積和を使って過去最高のスコアが取れたため、とても嬉しい回でした。
過去に勉強したことが活かせると気分が上がりますね。
AHCラジオも明日あるそうなので、しっかり見ていきたいと思います。
Discussion