AHC053 参加記
はじめに
AtCoder Heuristic Contest 053の参加記です。
結果
76.0Gで358位、パフォーマンス1503でした。(提出ファイル)
短期コンテストでは水色パフォーマンスしか取れたことがなく、今度こそはという思いで臨みましたが、個人的には、厳しい結果に終わってしまいました。
本番はふるいませんでしたが、延長戦で本番6位相当の解法を作れたので共有します。
解法
- AはLを50個と、残り450は区間[1, (U-L)/4]で指数的補間したものを生成
- Xは焼きなまし法
Aの生成
Lを作るパターン
いくつかのアイデアを試した結果、最終的な解法は、「AはLを50個、残り450は区間[1, (U-L)/4]で指数的補間(指数0.1)したものを生成」です。気持ちとしては、まずは大きい部分をLで確実に埋めて、残りの部分は大小様々なカードを作っておいて、あとは割当のフェーズで最適化すればよい、というものでした。
区間
区間についてはいくつかのバリエーションを試した結果、区間[1, (U-L)/4]としました。
補完
補完の部分は以下のバリエーションを試しました。大きな差には繋がりませんでしたが、最終的には指数を選びました。
- 線形
- 指数
- 対数
- フィボナッチ数列
- 位取り
コンテスト後半は、このあたりのバリエーションを色々試していたのですが、本質的な改善にはつながっていなかったように思います。コンテスト終了後にXのTLなどをみていても、二桁順位の方は大体これらのバリエーションでバラけており、自分とのギャップがわかりませんでした。
Lを作らない
Lを50個作らずに、[L,R]オーダーの値をN等分して各山の枚数をN枚にする方針(延長戦記載のRafbillさんの方針もそう)も試してみたのですが、先程の方法よりもやや悪い程度でした。時系列的には、こちらを先に試したのですが、枚数制約もあり極端に小さい端数などを調整しにくいのが欠点かと思っていました。実際、先程の方法にすることでスコアもやや改善したので、コンテスト中にこの方針は捨てました。今思うと結局、Xへの割当の最適化が甘かったので良し悪しは当時も今も判断できないです。
焼きなまし法
近傍は4種類を用いました。いずれもカード1枚のみを対象としました。
- 山↔捨ての入替
- 山→捨ての取り除き
- 捨て→山の追加
- 山↔山のスワップ
延長線で判明しましたが、山ごとに操作対象カードを1枚としたのが悪手だったようです。[1,対象の山の枚数]からダンダムに複数の枚数も選択できるようにすると、スコアが有意に上がりました。
おそらく、以下の問題を抱えていたように思います。
- 探索効率が悪く、改善が十分回っていなかった
- 1枚交換では局所的な改善になってしまっていた
敗因としては、以下の考察および状況から交換枚数を変更する実験をしない判断をした部分かなと思います。
- 考察
- 1枚交換でも十分な回数を回せば、複数枚交換した解に到達可能である
- ループ数は比較的多く回っていた(1Mループでも数百ms程度)
- ループ数を増やしても大きくスコアが改善しない
- 状況
- 短期コンテストであり、色々試せない
- 二段階の問題でありAの生成にも課題がある可能性がある
延長戦1(267位相当)
以下の改善を行いました。
- 区間[(L-2e+12)/8, (U+2e+12)/8]での一様乱数
- Rafbillさんのポストを参考にAの作り方を変えました。
- 近傍は2種類で、入れ替え対象枚数は1~8枚
- 山↔捨ての入替
- 山↔山のスワップ
区間はRafbillさんのpostを参考にしました。
本番相当で、79.7Gで267位、パフォーマンス1654でした。
正直、これでもまだ二桁順位に入れていない理由がわかっていません。何度か見返していますが、どこかにバグがあるのかもしれないです。。
延長戦2(6位相当)
こちらを見て、3枚の組み合わせの全探索というシンプルな方針に自分のスコアが達していたなかったため、追試することにしました。また、全探索を少し発展させることで、より強力な方法が見つかりました。
- Aは区間[(L-delta)/K, (U+delta)/K]での一様乱数で生成
- 50の山へのK枚ずつのカードの割当を探索します。（山に対するループは貪欲で、決まったカードから除外します）
- K<=3では全探索で間に合います。
- K>=4では全探索だと、計算量が多すぎるので空間を狭めます（偏りすぎた組み合わせを減らす）。区間の上半分と下半分それぞれに分けて、それぞれでK/2の全組み合わせを作る。組み合わせの和でソートしておくことで下半分配列(sumArrayL)の先頭、上半分配列(sumArrayU)の末尾から2ポインタで進め、|sumArrayL + sumArrayU − target| を最小化する組を探します。
| K | delta | スコア | 順位 |
|---|---|---|---|
| 2 | 2e+12 | 81.4G | 239位 |
| 3 | 2e+12 | 97.4G | 74位 |
| 2+2 | 2e+12 | 105.4G | 35位 |
| 3+3 | 4e+12 | 126.4G | 6位 |
3+3などではdeltaを増やさないと安定しませんでした。おそらく、区間を2つにわけたことでLやRに近い値を作りにくくなるため、範囲を広く取ったほうが良いのだと思いました。
これらの結果を見て思うのは、今回の問題は割当の最適化の部分が肝だったのだと思います。いきなり焼きなましても、うまく解空間を探索できておらず、乱択や効率の良い探索をする（その上で時間が余れば焼いても）のが良かったようです。山札の枚数をK枚に固定するのも、解空間を狭めてしまうのであまり良くない感覚がありましたが、実際はこの程度のKで固定であってもかなり誤差を小さくすることができたようです。
今回も勉強になりました。
Discussion