AHC031に参加した - ごらくらいふ

MC Digital プログラミングコンテスト2024（AtCoder Heuristic Contest 031）に参加したので、問題を解いた過程を記録してみた。

問題
サンプルをベタ移植
すべての予約を縦割りで割り当てる
しばらくコスト算出の実装に精を出す
コストについて考えた
イベントスペースを長方形のセクションに分割する
セクションの分け方を実験した
複数ナップサック問題？
余裕のあるところに詰めてもらう（雑実装の解消）
システムテスト
やりたかったこと

問題

atcoder.jp

W x W のグリッドで表現されるイベントホールがある
D 日分の予約群があり、日毎に N 件の予約がある
各予約には使いたい面積がある
- スペースの確保は長方形で行われなければならない
- 予約スペースは被ってはいけない
- 要求面積より余分に大きいスペースを貸し出してもよい
各予約スペースを区切るためにパーティションを設置する
- この辺の長さ 1 に応じて設置コスト、撤去コストが 1 かかる
- 日付をまたいだとき、パーティションに変更がない箇所はコストがかからない
- 要求面積に満たない区画しか貸し出せなかったとき、不足面積 x 100 のコストがかかる
たとえ少ない面積でも、すべての予約に場所を用意しなければ WA
なお、初日のパーティション設置コストは特別に 0 とする
コストができるだけ小さくなるようにする
制約
- W == 1000
- 5 <= D <= 50
- 5 <= N <= 50

サンプルをベタ移植

ちょっと問題を掴み取れていなかったので、サンプルをベタ移植した
幅を 1 に、高さを W のほっそい区画を全件用意するもの
Score: 107_822_101_150

https://atcoder.jp/contests/ahc031/submissions/51728038

すべての予約を縦割りで割り当てる

サンプルを基盤に、高さ W のまま、幅を調整して割り当てることにした
大雑把な実装なので、最低限である幅 1 は各予約に用意する
余分にスペースを確保すれば、チリツモで空間が足りなくなるので、大きい面積を要求する予約から割り当てた
Score: 264_827_950

https://atcoder.jp/contests/ahc031/submissions/51734984

しばらくコスト算出の実装に精を出す

今回、インタラクティブ問題ではないこともありコスト算出ツールがないので自前実装した
使う場面が来ればいいなという思惑
不足コストは比較すればよいので簡単
パーティション設置のコスト算出は、ABCで解くような問題に感じて楽しかった
- 水平方向と垂直方向に線分をわけて考える
- 線分の始点と終点で加減算して一つの線分へ合成したり（パーティションを求める）
- 当日と前日それぞれのパーティションの始点と終点で加減算して撤去・敷設を求めたり

type PartitonEvent = (usize, usize, isize);
type AlignedPartitions = HashMap<usize, Vec<(usize, usize)>>;
fn partition_by_event(event: &Vec<PartitonEvent>) -> AlignedPartitions {
    let mut partition: AlignedPartitions = HashMap::new();

    let mut state = 0;
    let mut begin = 0;
    for (level, point, volume) in event.iter() {
        // FIXME: hardcode
        if *level == 0 || *level == 1000 {
            // 外周部は壁なのでパーティションはいらない
            continue;
        }

        if state == 0 && *volume == 1 {
            // 0から1に変わるとき線分が始まる
            begin = *point;
        } else if state == 1 && *volume == -1 {
            // 1から0に変わるとき線分が終わる
            let line = (begin, *point);
            if partition.get(&level).is_none() {
                partition.insert(*level, Vec::new());
            }
            if let Some(v) = partition.get_mut(&level) {
                v.push(line);
            }
        }

        state += *volume;
    }

    partition
}

コストについて考えた

コスト算出が実装できたので、手元で試行錯誤できるようになった
いじっては数字を観察し、コストについて考えた
- 予約ひとつの必要とする外周の長さは、正方形に近いほうが小さい
- 予約スペースがパーティションを共有すれば、その分コストが安くなる
- 正方形を敷き詰めると、パーティションの置き換えが発生してコスト高になりそう
- 最初に設置したパーティションはコストの算定外になる
正方形のイベントスペースを長方形に区切って固定してしまえば、パーティションの置き換えを短辺の分だけで済ませられるのではないか

イベントスペースを長方形のセクションに分割する

正方形のイベントスペースを長方形の集まりとみなすことにした
W は 1000 固定なので、割り切れる数はハードコードできる
最も大きい面積を要求する予約を基準に、正方形の分割数を決めた
未使用スペースの多いセクションから順に割り当ててみた
また、前日と当日で必要とするスペースが大きい方に、予約スペースをあわせてみた
Score: 61_243_541

https://atcoder.jp/contests/ahc031/submissions/51763370

セクションの分け方を実験した

全日程を通して大きい予約を基準にセクション数を決定している
日ごとに最も大きい予約を基準に分けるとどうなるか
- -> 大半のスコアが悪化した
  - 分割数が 2 と 4 を往復したりして、都度 2000 の撤去コストが発生したりした
引き続き、全日程の予約を通して最も大きいものを基準とすることにした