MC Digital プログラミングコンテスト2024（AtCoder Heuristic Contest 031）に参加したので、問題を解いた過程を記録してみた。
- 問題
- サンプルをベタ移植
- すべての予約を縦割りで割り当てる
- しばらくコスト算出の実装に精を出す
- コストについて考えた
- イベントスペースを長方形のセクションに分割する
- セクションの分け方を実験した
- 複数ナップサック問題？
- 余裕のあるところに詰めてもらう（雑実装の解消）
- システムテスト
- やりたかったこと
問題
W x Wのグリッドで表現されるイベントホールがあるD日分の予約群があり、日毎にN件の予約がある- 各予約には使いたい面積がある
- スペースの確保は長方形で行われなければならない
- 予約スペースは被ってはいけない
- 要求面積より余分に大きいスペースを貸し出してもよい
- 各予約スペースを区切るためにパーティションを設置する
- この辺の長さ
1に応じて 設置コスト、撤去コストが1かかる - 日付をまたいだとき、パーティションに変更がない箇所はコストがかからない
- 要求面積に満たない区画しか貸し出せなかったとき、
不足面積 x 100のコストがかかる
- この辺の長さ
- たとえ少ない面積でも、すべての予約に場所を用意しなければ
WA - なお、初日のパーティション設置コストは特別に
0とする - コストができるだけ小さくなるようにする
- 制約
W == 10005 <= D <= 505 <= 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 の撤去コストが発生したりした
- -> 大半のスコアが悪化した
- 引き続き、全日程の予約を通して最も大きいものを基準とすることにした
複数ナップサック問題？
- 全日程を通してセクション数を統一するということは、各予約面積に割り当てる高さが固定になるということだった
- つまり、容量1000の容器がいくつかあって、各予約が必要とする面積（＝実質は幅）を割り当てればよさそうだ
- それは複数のナップサック問題ということか
- それって難しいやつでは…？
- あぶれた予約は、一番大きい予約から場所を分けてもらうことにした（雑実装）
- とりあえずテストケースは通った
- 多くのセクションで端まで使うことが増えたため、その分のパーティションが減らせるようになった
- Score:
58_509_946
https://atcoder.jp/contests/ahc031/submissions/51763370
余裕のあるところに詰めてもらう（雑実装の解消）
- どうしても余分にスペースを確保しているので、収まりきらない予約のために詰めてもらったりした
- あぶれた予約の対処が雑だったので、丁寧に詰めてもらうようにした
- 余分にスペースを調達している区画から削っていった
- 塵も積もれば山となるらしく、かなりコストを削減できた
- Score:
18_631_300
https://atcoder.jp/contests/ahc031/submissions/51766245
システムテスト
- 燦然と輝く TLE x3
退場処分になりました- 200位付近だったのに
- 2000ms 付近は危険領域だったか～
- 信頼できるのは 10ms まで
- 261位になりました
- 該当部分のみ相対スコア0点になるが順位参加を許された
https://atcoder.jp/contests/ahc031/submissions/51939513
やりたかったこと
- 前日の予約と当日の予約でどんどん大きい方を採用していったが、余分に確保しているスペースが多い予約だけを削れればパーティション構成の変更は少なかったのではないか
- ナップザック問題を解いて最後に集まったセクションは、細切れの予約が多く余白も多々あることから、コストの少ない配置方法をさがせるのではないか
AHC 青パフォとなって水色になれました。今後も頑張ります。
