【AHC031】緑コーダーの競プロ参加記録 #10

igasu_7

2024年4月6日 13:22

今回はAtCoder Heuristic Contest 031です。
ヒューリスティックでも緑コーダーなのでタイトルそのままです。

結果は291位、perfは水色の1560でした。
AHCに敷居の高さを感じている方に「こんなもんでこれくらいの順位なんだ」と知ってもらえれば幸いです。

ヒューリスティックコンテストに参加しよう！

「AHCはレートが下がらないので参加するだけ得！」

コンテストによってはサンプルコードが与えられることもあります。それをそのまま提出するだけで緑perfが出たりしますし、サンプルから1点でも改善すればperfに200くらい差が出たりもします。

アルゴリズム部門のレートはあまり関係ありません。コンテストによっては開催期間が2週間くらいあったりするので気軽に参加してみましょう。

問題概要

$${W \times W}$$の大きさのイベントホールがある。
イベントは$${D}$$日間開催し、毎日$${N}$$個の団体が参加する。
$${d}$$日目の$${k}$$番目の団体は面積$${a_{d,k}}$$以上のスペースを希望している。
上手にスペースを割り振ってコストを最小化してね。
コスト1 : 各団体の希望面積に満たない分の面積 $${\times 100}$$
コスト2 : 長さ$${1}$$のパーティション設置・撤去に +1

本記事では、イベントホールを上から見て横方向を「幅」、縦方向を「高さ」と呼びます。
また、コスト 1 のことを「不満」と呼びます。

Step 0. サンプルコードを見る

サンプルコードは、$${N}$$個の団体に対して$${1 \times W}$$のスペースを貸し出します。

$${W = 1000, N \leq 50}$$なのでめちゃめちゃスペースが余りますね。
しかもかなり「不満」が大きいです。

絶対スコア: 107,822,101,150

seed 5 における49日分の動向を表したgifです。

gifアニメーションは公式が用意しているWeb版ビジュアライザの機能を使って生成しています。

サンプルコード
https://atcoder.jp/contests/ahc031/submissions/51513253

Step 1. 平等に分割する

それぞれの団体の希望に関係なくスペースを平等に分割します。

つまり幅は$${W}$$、高さは$${\Large\frac{W}{N}}$$とします。
$${W}$$が$${N}$$の倍数でない場合は希望面積の大きい方から順に高さを +1 します。

絶対スコア: 35,220,062,950

「不満」のある団体が赤色で表示されます。

提出コード
https://atcoder.jp/contests/ahc031/submissions/51517822

Step1.5. 毎日同じ配置にしてもよい？

各日程の$${k}$$番目の団体の希望面積$${a_{0,k}, a_{1,k},...,a_{D-1,k}}$$について、それぞれ最大値を計算します。

最大値にもとづいてスペースを割り当てて「不満」が出ないのであれば、毎日その配置でよくなります。

スコアは理論上最小の$${1}$$点を得られます。

Step 2. 「不満」が最小となる高さを探す

$${i}$$番目の団体に割り振ったスペースの高さを$${Hs[i]}$$とします。
幅は$${W}$$固定のままです。

$${(i, j)}$$を全探索し、$${(Hs[i], Hs[j])}$$を$${(Hs[i] + 1, Hs[j] - 1)}$$としたときの「不満」を計算します。
このとき「不満」が最小となった$${(i, j)}$$に対して$${Hs}$$を更新します。

この操作を、時間の許す限り行います。

操作回数が多いほどスコアが良くなると思ったので、ここで Python から Rust に切り替えました。

絶対スコア：107,574,550

こういうのを「山登り法」って言うんですかね？

絶対スコアベースの話になりますが、この解法でも400位後半～500位前半で水色 perf を取れていそうです。

提出コード
https://atcoder.jp/contests/ahc031/submissions/51524699

Step 3. スペースの幅と配置を調整する

幅が$${W}$$固定だと無駄が多いです。
よって、ある高さ$${h}$$について面積$${h \times W}$$の中に複数の団体をまとめて配置します。

$${h}$$を固定したときに$${k}$$個の団体$${i、i+1, ... , i + k - 1}$$をまとめられるかをしゃくとり法で検討します。
このとき、希望面積$${a_i}$$の団体のスペースの幅は$${\Large\lceil \frac{a_i}{h} \rceil}$$です。

$${h}$$は可能な範囲で全探索し、$${k}$$個のスペースの面積の総和$${s}$$として、余っている面積$${hW - s}$$が最小となる$${h}$$を最終的に採用します。

絶対スコア：57,830,441

提出コード
https://atcoder.jp/contests/ahc031/submissions/51676289

Step 4. もっと調整する

ビジュアライザを眺めていると、「不満のある団体が存在する」かつ「余分にスペースが割り振られている団体がある」ケースを見つけました。

余分なスペースは不満のある団体に再分配した方がよいですね。

高さを +1 したときの不満の減少量が大きい順に追加でスペースを割り振ります。優先度付きキューを使いました。
横一列に並ぶ団体はまとめて高さを増減させます。

また、スペースの高さ$${h}$$を決める際に「希望面積に対して過剰に割り当てられている面積の最小化」も考えます。

絶対スコア：34,439,735

提出コード
https://atcoder.jp/contests/ahc031/submissions/51686959

Step 5. 希望面積の累積最大を考える

各日程の$${k}$$番目の団体の希望面積$${a_{0,k}, a_{1,k},...,a_{D-1,k}}$$について、それぞれ最大値を計算します。
最大値にもとづいてスペースを割り当てて「不満」が出ないのであれば、毎日その配置でよくなります。

これはStep 1.5での戦略です。
この戦略を可能な日数の範囲で行います。

つまり$${i}$$日目から$${j}$$日目までの$${k}$$番目の団体の希望面積$${a_{i,k}, a_{i + 1,k},...,a_{j,k}}$$について、それぞれ最大値を計算します。

これは Step 1.5 と Step 4 の良いとこどりの戦略です。
最高で理論上最小のスコア、最悪でもStep 4 のスコアが得られます。

絶対スコア：24,343,302

提出コード
https://atcoder.jp/contests/ahc031/submissions/51702937

ちょっとでもスコアを良くする

ここから大きく改善する方法が思いつかなかったので小銭稼ぎに走ります。

Step 6.1. パーティションをちょっと共有する

$${i}$$日目の最下段のスペースの高さを$${h_1}$$、余分な高さを$${s_1}$$として、同様に$${i+ 1}$$日目についても$${h_2, s_2}$$を求めます。

このとき、両スペースに対して同じ高さ$${h'}$$を割り当てることができればパーティションを共有できます。

つまり、$${h_1 - s_1 \leq h' \leq h_1}$$かつ$${h_2 - s_2 \leq h' \leq h_2}$$を満たす$${h'}$$が存在すればよいです。
これは$${S = \mathrm{max}(h_1 -s_1, h_2 - s_2), T = \mathrm{min}(h_1, h_2)}$$として$${S \leq h' \leq T}$$と言い換えることができます。

参考： Atcoder Beginner Contest 343 - E - 7x7x7

絶対スコア：23,900,435