Skip to content

MC Digitalプログラミングコンテスト2024(AHC031)

問題概要

  • W * Wのグリッドで表現されるイベントホールがある
  • D日分の予約状況が与えられるので、条件を満たすような長方形区画を用意したい
    • 各日の予約数はすべてN個で、各日・各予約での必要面積が与えられる
  • 長方形区画は、外周またはパーティションで区切られている必要がある
  • パーティションは設置か撤去した場合コストが発生する
  • また、各予約の必要面積よりも小さい長方形区画だった場合もコストが発生する
  • できるだけコスト合計が小さくなるよう、全部の期間での各予約の長方形区画を決定せよ

時間

  • 240 時間

個人的メモ

  • 任意形状は扱いにくいため、なんらか扱いやすい形を思いつけるか・探索できるかがポイントだったかも

各予約の面積の分布

コスト

面積不足コスト

  • 面積不足のコストは、「足りない面積*100」もあり、壁再設置コストよりも影響が大きい
    • そのため、可能な限り面積不足コストが0になるのを目指す必要がある
  • 単純な解法として、幅W * ceil(必要面積a/W)の長方形を埋めていく方法が思いつくが、面積1001とかの場合、1000*2=2000分の面積を確保することになり、999だけ無駄に確保することになる
    • これが繰り返されることで、空きに余裕がないケースでは面積不足コストが発生してしまう可能性があり、このアプローチでは常に面積不足コストを0にできるとは限らない
  • しかし、ほとんどのケースでは面積不足コストは0にできるため、どちらかというと壁設置コストを減らす勝負だった

壁のコスト

  • 壁は、再設置に対してコストがかかるため、最初から最後まで置きっぱなしにできるとコストは0にできる
    • 初日と最終日の設置・撤去コストが0
  • したがって、できるだけ壁を設置しっぱなしにしたく、可能であれば最後まで動かさないような壁が作りたい
    • 全期間が無理でも、数日間だけでも動かさないような壁をできるだけ作りたい
  • 面積に余裕があるようなケースでは、全期間で壁を動かさなくても予約を割り当てできるケースが作れ、そういうケースはコスト0が達成できる
    • システムテストの2000ケースでは28ケースあった模様

アプローチ

壁の形状

  • 短冊形(梯子形、あみだくじ形)
    • 「最初から最後まで動かさない壁」として、短冊形(領域全体に対して縦方向にいくつかの領域に分ける)にした領域を用意
      • (縦派と横派がいるが、ここでは固定壁は縦方向で考える)
      • 各短冊内について、横方向に壁を作って区切る
    • もしうまく入れられる場合は、各短冊の横方向の幅の分だけしかコストが発生しないため、再配置してもコストを抑えられる
      • 各予約の長方形の横壁部分のコストが0にできる感じ
  • 二分木形(木構造)
    • 領域全体に対して、2つの領域に分けるのを再帰的に行う
      • ただし、片側に1つの予約しか割り当てない(長方形を順番に1つずつコストが低い方向にカットしていく)とかにすると、階段状みたいな感じ(縦横の繰り返し)になってあまりいい形にならない
  • 任意形状
    • 雰囲気は、AHC001の指定点がないケースっぽくも見える
    • 任意形状・任意位置になるので最適解を内包してそうにも思われるが、自由度が高すぎて探索が大変で、今回の問題で任意形状で上位の人はいなそうだった

短冊の形状、予約の割当、の探索

  • 各短冊(全期間で固定する縦方向の壁)について幅や個数をどうするか、各予約の割り当て方・順番をどうするか問題になる
    • 幅が小さいものばかりだと、横壁のコストが小さくなる一方で、十分なサイズの短冊がなく面積が大きい予約で面積不足になる恐れがでる
  • 乱択&入れられるか判定
    • ランダムに個数と幅を生成して、「予約の面積が大きい順に一番面積の空きがある短冊に割り当てる貪欲」で入れられるかが判定できる
      • (AHC025とかでは幅がすべて同じだったので、高さが一番低いやつにいれる貪欲とかだったが、正確には空き面積)
      • 実際のコストは、オーバーする面積や横方向の壁から計算
    • しかし、うまくいく個数や幅の状態に対して、それを少し変化させた状態も良い状態である可能性が高いため、局所改善することが考えられる
  • 個数・幅の局所探索&判定
    • 個数や幅を少し変えたりする局所改善を繰り返す
      • 大きく変化させるのが難しそうで、乱択や多点スタート的な要素が必要だったかも？
    • 予約の割り当ても、変化させる部分付近だけの変化で対応できる可能性があるので、割り当ても保持しておく
    • 短冊の横方向分割
      • 各短冊は、さらに横方向にカットすることで2つの短冊に分けることができる
      • しかし、全期間固定での横方向の分割が作れない可能性が高いので、(全期間固定も含めて)横方向壁は探索したほうがよい
  • 個数・幅、予約割り当ての局所探索
    • 予約の割り当て方も含めて局所探索する
      • 前半後半に分けて、前半を個数・幅(縦方向壁)、後半を予約の割り当て方(横方向壁)に分けてそれぞれ局所探索する
    • 近傍には「前日の区切り位置と同じにする」とか、「いくつかまとめて動かす」とか、「各短冊で一番大きい予約のみ取り除いて降順に貪欲再割り当て」とかの近傍も必要っぽい(解説放送)
  • 個数・幅、区切り位置の局所探索
    • 予約の割り当て方ではなく、ある短冊について「横壁をいれる(区切り)位置」を探索する
      • 予約の割り当ては、各区切りでできる領域の面積の降順に、予約の面積の降順に割り当てるのが最適なので、予約の順番は考えなくて良い

無駄にする面積が少ない分割

  • https://twitter.com/noimi_kyopro/status/1774741057361637845
  • ある長方形w,hの分割(縦に壁をいれる場合)について、予約の面積 mod hを考えると、0か、値が大きいほど無駄にする面積が少なくなるので、そのような予約の集合を見つけて分割する

外枠に接するようにするべきか

  • 外枠近くの長方形で、外枠に接しない形で長方形を作るのは、接することで壁設置コストを減らせるので、基本、接するようにしたほうがよさそう
  • ただ、空きに余裕があるケースの場合とか、短冊内での空きを許容するほうが自由度が高いと思われるので、常に空きを作らないのが最適ではなさそう

隣接長方形での壁の横置き、縦置き

  • https://twitter.com/wata_orz/status/1774742927757226059
  • 短冊形などで、幅が同じで高さが異なる長方形が隣接している場合、もし高さの合計が幅よりも小さければ、横方向ではなく縦方向に区切ったほうがコストが小さくなる
    • 3つ以上でも、コストが小さくなる方向に分割を繰り返す、局所的に二分木形で考える、などできる
  • 改善はするが、短冊解では幅がもともと小さかったりするので、そこまで改善幅は大きくないっぽい
    • 入力が小さいケースとかでは効いてるかも？

その他

緊急退避

  • メインアプローチがうまくいかない場合に、あきらめて単純な別の手法に切り替える
    • ほぼ0点になるぐらいなら、少しでもスコアを稼ぐことを目指す

関連問題

First-fit-decreasing bin packing

部分和DP

  • N個の整数から何個か選んで総和をAにできるか？
  • dp[i+1][j]:=i番目までの整数からいくつか選んでjにできるかbool

他の分割生成の仕方

  • 等分割
  • 二べき的に分割(1,2,4,8,...)
  • 今回の入力生成のように区間に一様乱数を何回か打つ(指数乱数生成)

特徴的なケース

  • seed=34
  • seed=111
  • seed=116
  • seed=288
  • seed=922

ビジュアライザ

解説

(50位まで&発言を見つけられた方のみ)