MC Digital プログラミングコンテスト2024(AHC031)に参加しました。
問題名はEvent Hall。複数次元の充填問題でした。
結果は1064人中98位。（事前テストは88位）
問題
1000*1000のホールを複数日(D=5～50)、複数の予約(N=5～50)に対して分割して貸し出すよ。
面積不足やパーティションの設置/撤去を減らそう。
考察
高さ1000で千切りすると*1、予約ごとに無駄な面積が0～999発生する。また、予約ごとに1000のパーティションコストが発生する。
高さ500で分割すれば、無駄は0～499に抑えられる。また、予約ごとに500のパーティションコストが発生する。ただし余った幅は捨てることになる。高さの分割線は引きっぱなし、かつ初日コストは免除されるので実質無料。
なるほど、つまり段を増やしまくって面積ロスやコストを減らしましょうという問題？そのためには段ごとの余りを減らすのが必要になりそう。
あとは段数は一旦固定するものとして、高さを先に決めて予約を充填するのか、予約を分配して高さを計算で求めるのか。ここはまず適当にやってみるか。
あとは面積ロスのペナルティが大きいのでそっち特化の緊急解法も用意したい。縦横に面積ロスが小さくなるよう残りスペースを貪欲に切ればデッドスペースはかなり小さくなるはず。
実装
エコ方針で、最終的にやったことだけ書く。
基本的に貪欲で、条件を少しずつ変えながら回す。
1周目、段数を仮定(1～N-1)して貪欲。
全日の予約を纏めて大きい順にソートし、大きい順に配置する段を決める。
優先順は、入る中で空きが小さい段、新しい段、入らず過剰量が小さい段の順。
2周目、小さな過剰*2を認める貪欲をしながら、最善解で使用率の高い1段ずつ割り当てを固定する。
時間がかかるので、最善スコアの段数に対して-1～+3段を試行する。最善を更新したときは範囲もずらす。
大半はこの解法で出てきたのが最終的な回答となる。
3周目、別解で段の容量を一部ずつ先に決めながら貪欲。
容量を1000ずつずらして探索するアホアホ探索、しかも段ごとに容量を貪欲で決めているので、時間の足りなさもありこちらが刺さるのは全体の25%くらいのケース。
一旦仕上げ、ここまでの最善解から、面積不足の日を縦横に貪欲カットする解法で改善できないか試みる。
また、全日を貪欲カットする解法も一応試す。
これでも時間が余ったら、最善解+1段ができないかを焼きなましで試みる。
その段数の最善解をベースに、1予約を別の段に移動、別の段の予約同士を交換、で焼く。
ここまでやって最善だったものを最終解とする。
他の人の解法を見て
上位の基本解法は各段の容量を焼くっぽい。序盤の初期解が悪い時代に割り当ての焼きなましが上手く行かなかったことや、貪欲が弱い時代を引きずってそちらに手が伸びなかった感がある。
感想
他の方針と共存/転換しやすいものだけで場を繋いでしまったので、良くも悪くもそんな順位に落ち着いた。
理論値が出せる極端なケースなども含め、パラメータで向く方針が違うのでどれだけ手広くカバーできるか（時間を注げるか）だったり、あるケースでコストを半減させても相対スコアの低いケースでは無意味という、相対スコアの嫌なところが出やすい問題だったと思う。
爆死覚悟で方針決め打ちしないと今後レートを伸ばすのは厳しいかなぁ。
