AHC031
問題
パーティションをできるだけ動かさずに、いい感じの大きさで部屋を作って欲しい。
初日のパーティション設置だけ無料。2日目以降は変化した分に比例したコストがかかる。
要求面積に足りない部屋があったらその分は莫大なコストとして計上される。
ビジュアライザ結果
seed=0 (3628) | seed=1 (121548) | seed=34 (631048)
https://scrapbox.io/files/660b468423faf6002481d06e.gifhttps://scrapbox.io/files/660b458de588fb0025c11bc3.gifhttps://scrapbox.io/files/660b4597318254002438a6ce.gif
解いた方法
まずは縦線を引いていくつかの短冊状にする。この縦線は日毎に動かしたくないので、全日程を加味してもっとも大きい面積を基準にする。日によっては短冊に余りの面積が出るので、そこに小さい部屋を埋めていく。
これだけだと面積不足のペナルティが出ることがある。その場合は乱択をする。ペナルティが0になることに加えて、前日と比べて短冊内の部屋数が一致してる方が良いスコアとみなすような評価関数も使って時間いっぱい回す。
最後に短冊内の横線を上下に調整する。面積不足が起こらない範囲でなるべく前後の日で横棒を共有できるように頑張る。
もっとやれたな〜ということ
ビジュアライザの改変
今回、標準のビジュアライザだけで分析することが難しかったので、色やテキスト情報を増やすだけでも結構違いそうだった。
焼きなまし
短冊をスワップしたり、短冊内で上下にスワップしたりということはできそうだった。ただ、今回はスコア計算を実装に加えていないので諦めてしまった。