[MC Digital プログラミングコンテスト2024] AHC031
暫定57位->システス58位でした。
https://atcoder.jp/contests/ahc031/submissions?f.User=merhorn
ペナルティが2種類あって
1. 予約面積に足りない場合はarea_cost * 100のペナルティ
2. パーティションを消す/設置する場合は、距離のline_cost * 1がペナルティ
明らかに1.が重たいので、最初の目標はarea_costを0にすることにします。
1日目
とりあえず簡単に実装したいと思います。ABCのD問題で「大きな正方形に、小さな長方形を隙間なく詰められますか？」を判定する問題がありました。
左上に長方形を接着させて試せばいいという解法が直感的に結びついたので実装します。
9割くらいのテストケースで、area_cost = 0を達成できました。
2日目
20位くらいにつけて、幸先のいいスタートを切ります。
前日のパーティションを気にしなければ、横縦横縦…と仕切りを設置する置き方はそれなりにコスパがいいようです。
さて、順位表をみると、ぴったり1,000,000,000点が何人かいます。
テストケースのどれか1つで、理論値解がとれるんでしょうね。
予約している面積が
day1 = {10, 20, 30, 40, 50}
day2 = {15, 20, 35, 40, 45}
day3 = {18, 22, 32, 39, 40}
とかだとする。
それぞれ最大値をとった
max = {18, 22, 35, 40, 50}
の大きさの仕切りを初日に設置して、Score = 1を得られました。
3日目
area_cost = 0にした次は、いよいよパーティションの移動ペナルティline_costをできるだけ小さくしたいと思います。
左上設置方だと、焼きなましに発展させにくいので却下。
初日に横線で適当に区切りを入れて、階層分けしたらどうだろう？
階層を固定してしまえば、かなりline_costを削減できると思いつきます。
階層を乱択して、area_cost = 0を目指します。これが最後まで使う方針になりました。
4-8日目はおやすみ
9日目
気づけば…あと2日…。仕方ないね。
階層固定したあとの焼きなましを考えます。
最初の1秒は階層のランダムプレイアウトで、いい感じの初期解を5個選びました。
のこり2秒で焼きなまし。
部分的な日数で理論配置ができるか探したり
階層を+-1ずらしたり
階層を1つ増やしたり
階層を1つ減らしたり
して、スコアを少しでも稼ぐようにします。
10日目(最終日)
area_costを0にできない厳しいケースが1割くらいあります。
初日の解法をマシにするため、Dijkstraしました。
日毎に、area_cost = 0な出力を20パターンほどメモしておいて、line_costをコストに見立ててDijkstraをします。
絶対スコアがかなり下がるので、目に見える総得点が下がって気持ちいい！！！！のに、順位はほとんど変わらない相対スコアの罠。
階層も動きますが、たまに同じ階層を得られた場合にline_costを節約できています。
後悔
そもそも、もっと焼きなましに身を投じたいですが、焼き思考にいききれない歯がゆさがあります。部屋の入れ替えをするなど、したかった。
次に、このまま貪欲思考で行くとして、visualizerを見てもまだまだ隙があり、詰めきれていません。
特に理論値とる方法をもっと応用したいところでした。
あと1日あったとして、盤面全部ではなく、部分的な理論値セットを採用して、一部フロアを固定をするなど。
スコアをもう一段階大きく減らせるんじゃないかという伸びしろを残しておしまいです。