MC Digital プログラミングコンテスト2024（AtCoder Heuristic Contest 031）に参加しました。結果は4位でした！
コンテストページ
解法
主に3つの解法を使いました
①コスト0狙いの2分割貪欲
②短冊状に分けて、短冊内の区切り線を焼きなまし
まず①でコスト0の解を探索し見つかれば終了。
次に、何個の短冊に分けられるかを計算します。2個以上の短冊に分けられるなら②の解法を使い、そうでないなら③の解法を使います。
①コスト0狙いの2分割貪欲
全ての日の予約を1日分にまとめます。（k番目の予約ごとに全ての日のmaxサイズをとる）これで1日分のN個の予約を割り当てる問題になります。
N個の予約を面積合計ができるだけ同じになるように2つのグループに分けます。（予約を面積大きい順にソートして小さいグループに割り当ててく貪欲）
そして、グループの面積比で区画を2つに分けます。
それぞれの区画を同様に再帰的に分けていき、グループ内の予約数が1個になったらその予約に対応する区画が決定します。
すべての予約の面積を満たせるならコスト0の解が見つかったということになります。
※この解法はコスト0にできるケースで確実に解を見つけられるわけではありません。
何個の短冊に分けられるか
短冊数を仮に決めて、それが予約面積を満たせるかどうかを判定することで二分探索的に決めました。
予約面積を満たせるかどうかは、予約を1個ずつ短冊に割り当てていく評価値貪欲をします。割り当てたことで各短冊の必要な太さが決まり、短冊の太さの総和が1000以下なら予約面積を満たせます。
②短冊状に分けて、短冊内の区切り線を焼きなまし
前の処理で求めた予約の割り当てをもとに、区切り線の初期位置を決めます。
以下の遷移を使って焼きなましをします。
- 1日の区切り線1個を、その短冊上で少しずらす
- 同じ場所にある複数の日の区切り線をまとめて、その短冊上で少しずらす
- 1日の区切り線1個を、その短冊上で前後の日の区切り線と同じ場所に移動する
- 同じ場所にある複数の日の区切り線をまとめて、その短冊上で前後の日の区切り線と同じ場所に移動する
- 1日のランダムな場所に区切り線1個を持ってくる（他の短冊からも持ってくる）
- 区切りの線を選び、前後の日の同じ場所に区切り線を1個持ってくる（他の短冊からも持ってくる）
- ある短冊から別の短冊に太さを1移動させる
- 1つの短冊の太さを-1か+1する
評価値は生スコアをそのまま使用。
生スコアを計算するために、どの区画にどの予約に割り当てるかを決める必要があります。区画を面積順ソートして大きい予約から大きい区画に割り当てるのが最適なので、毎回ソートして決めます。
遷移してソートして評価、遷移してソートして評価、遷移してソートして評価・・・みたいな感じ。ソートの処理時間がボトルネックでした。
ビジュアライザ
横短冊派
③空間と時間の区間を持つ木構造の焼きまなし
木構造。各ノード（頂点）は以下の情報を持つ
- 担当区画
- 担当日の範囲
- 各担当日の予約リスト
ルートノードではすべての区画、すべての日、すべての予約リストを持つ。
頂点について次の2種類の分割のどちらかを行って葉まで再帰的に展開する。
(1)担当日を何個かに分けて子ノードを作る
(2)区画と予約を2分割して子ノードを個作る
この後、ランダムにノードを選び、その子ノードを破壊～ちょっと変更して再生成の焼きなましを行う。
この解法のスコアはかなり悪くてあまり良い解法ではなさそうです。
ビジュアライザ
その他工夫：日付の圧縮
何日か分の予約をまとめて1日として扱うことで高速化しました。まとめた日はすべて同じ区切りとして出力するため、まとめた日の間の区切りコストは0になります。
その他：Wladimir Leite さんの作ってくれた統計情報
https://wladimirleite.github.io/ahc031.html
右のほうが予約面積が大きいテストケースです。
予約面積が大きい部分は解法③が使われるはずで、スコアが悪いことがわかります。
感想
コンテスト序盤～中盤は、領域を2分割していくような木構造で考えていて実装が難しかった。難しい実装をしたのに順位は全然上がらないので、何かしらシンプルで強い解法があることは予感していたが、なかなか見つけられず。
短冊解法はコンテスト終盤で思いついて、実装も簡単なうえに高速化するほどスコアが上がって面白かった。短冊数を決めるところは時間が無くて検討できなかったので、そこで差がついているのかなあ。ぐぬぬう……
