AHC040参加記
初めに
2024/11/29(金) ~ 2024/12/9(月)に開催されていた、長期プログラミングコンテストHACK TO THE FUTURE 2025 （AtCoder Heuristic Contest 040）に参加しました。
ルールベース初期解 + 山登りというかなり単純な手法で、本番275位を取ることができました。以下、思考過程の記録を残します。
今回良かったこと
- ルールベースの初期解は、AHCラジオで紹介されていた方法で作れていた
- 「山登り法」というものを明示的に理解して使えた
ルールベース初期解
入力生成の項目を見ると、段ボールの実際の辺の長さは、必ず[10^4, 10^5]の範囲です。
A = 5×10^4 × sqrt(N) × 1.2 ~ 1.3 として、A×Aの正方形を作ることができれば、大まかに充填率80%程度にできそうな気がします。
長方形を全て縦長にしたうえで横に積んでいき、幅がAである「Aブロック」を作ってみます。
工夫点としては、各「Aブロック」ごとにクエリを出して実際の大きさを測定し、予想より大幅に小さい/大きい場合には段ボールの数を増減して調整する処理を加えました。
これを縦に積みます。 ⇒ 『状態1』
最終列を横倒しにすると、場合によってはスコアが改善します。 ⇒ 『状態2』
また、最終列を削って、横から付け直すと、場合によってはスコアが改善します。 ⇒ 『状態3』
この『状態1』『状態2』『状態3』のうち、一番スコアが高いものを、ルールベース初期解としました。
山登る
Aブロックの計測がsqrt(N)回、そのあとの結果出力が3回なので、N = 30の場合でもsqrt(N) + 3 = 9 <= 15 = N/2となり、確実にターン数が余ります。
なので、残りはとにかくランダムに回転させてみて、スコアの向上を狙いました。 「ランダムに回転した結果スコアが向上したら、それを新しい拠点にして、また回転させていく」 という山登り法を実装したところ、順位が50～100位ほど上がったようでした。
参考資料
「山登り法が何か知らない」 ⇒ terry_u16さんのスライドがとても分かりやすかったです。
「山登り法の実装が分からない」 ⇒ kaede2020さんのYouTubeがとても分かりやすかったです。
最終結果
私用が重なったこともありこれ以上の改善はできませんでしたが、最終結果は275位で、ギリギリ初の青パフォーマンスを取ることができました。
ソースコードはこちら。
終わりに
AHCラジオでも紹介されていた筋の良いルールベース初期解を思いつけたことと、「山登り法」という名前を明示的に理解できたこともあり、個人的にはある程度満足のいく結果でした。
一方で、まだまだ行けるのでは？という気もしており、AHCラジオで話があった『階段状に積んでいき、残り面積を評価関数にしてビームサーチする』という方法や、『カルマンフィルタによって真値を推定する』という方法など、延長戦でいくつか試してみたいと思います。
そもそも『ビームサーチ』や『カルマンフィルタ』を明示的に理解するところから始めないと。。。まだまだ先は長そうですが、一歩一歩学んでいきます。
Discussion