AHC031参加記【最終72位】

解説
- 最終解法の概要
- 提出コード
参加記

解説

最終解法の概要

　平均空き面積 $E$ によって、複数の解法を切り替えています

　共通区画幅焼きなまし解を適用するケースが最も多かったです
　下図のような、縦長のエリアを全日使うことを考え、この幅を焼きなましによって探索します
　日を跨ぐことによるパーティションの変更は、この区画幅の中でのみ行われるため、そのコストを抑えることが出来るのでは。という思惑があります

　近傍は3つで、

20%で、分割数を増やす
10%で、分割数を減らす
それ以外の場合、2つの区画幅を乱数でリバランスする

　これによって得られた幅リストを降順ソートして使います
　幅リストを辞書のキーにしてスコアを保存しておくことで、スコア計算の頻度を抑えています

　スコア計算も、制約によって厳密な値まで計算するか、速度優先でざっくりな計算をするかを切り替えています

　幅リストから解の作り方は、希望面積の降順に最も面積余りの少ない幅の場所に割り当てていく貪欲で実装しています

　ちなみに、上記解法を適用できない場合は以下のような解になりました
　恐らく希望面積を満たせていないテストケースはないと思われます

提出コード

　pypy3です

atcoder.jp

参加記

はじめに

　せっかくの長期コンですが、事情によりコーディングに時間が割けません
　空き時間に細かく考察を進めて、効率よく頑張りたいです

　今回から、手元でNimを実行できる環境構築をしたので、高速化バトルになりそうであれば言語の持ち替えも行いたいと思っています

1.問題

atcoder.jp

　 $W×W$ のイベントホールを、 $D$ 日間、 $N$ 団体に貸し出したい
　希望面積以上の長方形区画を、出来るだけ境界を変更しないように分ける

　ホールサイズ $W$ は、1000固定
　日数 $D$ は、 $5\leq D\leq50$
　予約数 $N$ は、 $5\leq D\leq50$
　希望面積の総和は、 $W^2$ 以下が保証される

　希望より小さい区画を提供した場合、差の100倍コストがかかる
　日を跨ぐ際に、パーティションの相違があれば個数分コストがかかる

2.開始直後の考察

情報が全て出されている上、時間制限が3secなため焼きなましが強そう
用意した区画は、希望より大きければ良いため空きスペースは不要
大きい希望区画ほど、優先して希望以上の面積を提供すべき
小さい希望区画は、パーティションの変更量が少なく済みそう

解法のアイディア

全日程区画を固定した場合に、最小コストをなる配置を焼きなましで求める
→日ごとの希望面積昇順で区画は決めてしまう
最適に近い配置をいくつか持って、各日ごとにどの配置を使うか探索する
→パーティションの変更量も考慮する

3.区画固定焼きなまし

　最初の解法は、全日程区画を固定した場合に、最小コストをなる配置を焼きなましで求める方法にしました
　簡単のため、短冊状に区切って幅や高さを変更する近傍を使いました

　ACできるコードを投げましたが、当日24時頃で104位/208人とイマイチな結果です
　パーティションを移動させない<区画を満たす方が重要なようです
　次は、パーティションの変更を気にせずに、希望面積を満たせる解法を考えてみたいと思います

4.希望を満たす区画貪欲

　各日について、大きい区画から決めていく貪欲を作ります
　簡単のために、前の解法と同じく短冊所に区画を作り順番に詰めていきます

　収まらない場合、最大長方形を $O(N^2)$ で探索しそこに出来るだけ大きい区画で置くようにしました
　最大長方形のアルゴリズムは、以下のサイトを参考にさせて頂きました

ALGORITHM NOTE 長方形探索：最大長方形の面積 Largest Rectangle

5.短冊形貪欲解法

　焼きなましをしたい！と思い、AHC001のような感じで四角を動かして良い配置を探索しようとしましたが、どうもうまくコードが書けません
　各日の盤面だけならまだしも、日を跨いだパーティションの判定までやるのは骨が折れます

　考え方を変えて、探索可能そうな制約に置き換えることにしました
　具体的には、区画は全て上から下まで( $h=1000$ )使うものとする。としました
　これであれば、幅方向だけを見ればパーティションの増減が割と高速に判定できそうです

　ただ横に並べるだけだと、幅が1000を超えることがあるため区画を上手く併合する必要があります
　高さ $h$ は1000固定なため、希望面積 $s$ を満たす幅 $w$ は $w=-(-s//h)$
　その時、無駄となる面積は、 $m=h*w-s$ で求めることができます

　この無駄となる面積の大きい順に、併合する区画を全探索することで無駄となる面積を小さくした盤面を作ることができます　

　一旦この貪欲解法で投げてみるとスコア61,142,184を得ることが出来ました

6.短冊解法山登りver

　上で作った盤面を初期解として、区画の幅方向の順番を入れ替えてパーティションの変更によるコストを最小化していきます（縦方向の分割をしている横線は無視）

　全日程を同時に焼いてもいいのですが、2日目から順番に盤面を確定させていくと差分計算が簡単そうに思えます
　→後ろの日の盤面との差は考えなくてよい

　このような考え方で、幅方向の入れ替え近傍で山登りをした所スコア25,818,021になりました

　現状、幅方向に余った分については最後の区画を端まで伸ばす処理にしています
　余りを上手く使って、パーティションの共有ができると更にスコアが伸びるはずですが、余りを利用した遷移が難しいです...
　ただ、今の解法から伸ばすには避けられないので、頑張って考えてみます

7.オフセット遷移追加焼きなましver

　各区画について、オフセット量を記憶する配列を別で設けて、コストが下がるまで幅を増やしていく遷移を追加しました
　また、低頻度で全てのオフセット量を0にする遷移も入れています

　下は、seed=1のビジュアライザです
　所々黒い縦線になっていて、パーティションの変更が減らせていることが分かります

8.再考察

　8/25(月)時点で126位という状況です

　今の方針だと伸びしろがあまり無さそうなので上位の解法を想像してみます

　理想の盤面は、最初から最後までパーティションの増減が無く、全ての希望面積を満たすような形になるはずです
　そんな配置が可能なのか現実味がありませんが、どれくらいの密度の配置になるのか確認していなかったので、入力生成方法を読みます

　パラメータ $e=rand(500, 5000)/10000$
　平均空き面積 $E=round(W^2e^2)$ 　とあります
　実際に計算してみると、平均空き面積 $E$ は2,500~250,000の範囲のようです

　 $Td$ を求めて、集合 $S$ を生成して、、、と書かれています
　要は $Td$ は希望面積の累積値のようです
　こちらも実際に計算すると、625,000~998,750の範囲のようです
　最悪パターンでも、1,250は面積に余裕があるということは分かりました

　逆に最も余裕のあるケースだと、貪欲に実装しても満点を取ることができそうです

9.区切り幅を焼きなまし

　前の解法では、各日毎に区画をマージしていって幅を作っていました
　全日程で同じ幅を使うことを考えると、その幅の増減と区切り数の増減を近傍とした焼きなましをすると、良い解が得られるような気がします

　各日でその幅をどう使うかは、面積の大きい方から貪欲にあまりの少ないように詰めていきます（ここも探索した方が良さそう）
　貪欲に詰めていくだけでも、 $O(DN^2)$ くらい掛かって非常に重いですが、seed=0のような簡単なケースでは結構良いスコアを出すことが出来ました！

　一部のケースとはいえ、最良に近いスコアを出すことは相対評価スコアにおいてかなり重要なことなので、これを提出して100位以内に入ることが出来ました

　平均空き面積 $E\leq40,000$ の時は前の解法を採用するようにしたところ更に順位が上がりました！

10.満点解法の実装

　各N毎にD日間の希望面積の最大値で区画を用意すれば、コスト0を実現することができます
　ただ、 $N\leq5, D\leq5$ の一部のケースでしか実現しないため、現時点の順位にはあまり影響はないような気もします

11.平均空き面積が厳しいパターンの貪欲解法

　平均空き面積が $E\leq30,000$ の場合、「7.オフセット遷移追加焼きなましver」の解法を用いていましたが、途中まで各日で共通のパーティションを持てないか考えました

　探索で求める方法が難しいため、貪欲に解を作ってみます
　具体的には、全ての希望面積の内で最大のものを選び、一つの区画を作ります
　他の日は、その区画に収まるような組み合わせの内、最も面積のあまりが少なくなるように区画を分割して納めます
　この組み合わせは、 $dp\lbrack n\rbrack \lbrack k\rbrack$ n番目の区画までで、高さkとなるように選んだ場合の面積余りの最小値。のような感じのdpで求め、復元することで得ることができます