AHC069「Picnic」でやったこと

最終的には、コンパクトな形状をあらかじめ用意しておく貪欲をベースにしました。

ただし、置けるグループをすべて受け入れるとすぐに盤面が埋まります。また、空きマスの総数が足りていても、細かく分断されると大人数のグループを置けません。そのため、単に現在のグループをきれいに置くだけでなく、次のグループにも使いやすい空間を残す必要があります。

実装したものを大きく分けると、次の4つです。

1. 人数ごとに周長の短い形状を用意する
2. 盤面を分断しにくい場所へ置く
3. 混雑時は収益密度の低いグループを断る
4. 通常配置が難しい場合は、既存グループの再配置も試す

以下、それぞれについて説明します。

1. 解法の全体像

グループが到着したら、まず人数 \(P\) に対応する形状テンプレートを盤面上で動かし、衝突せずに置ける場所を探します。

テンプレートが置ける場合は、周長が短いことを最優先にし、その中で盤面端・池・長く残るグループに接する候補を選びます。盤面がかなり埋まっている場合だけ、配置後の空き連結成分も調べます。

テンプレートが一つも置けない場合は、空き連結成分から直接 \(P\) マスを成長させます。それでもよい形にならない場合は、移動費率 \(R\) に応じて既存グループの再配置を試します。

最後に、その配置から得られる1マス・1時間あたりの収益を、最近到着したグループの分布と比較して、受け入れるかどうかを決めます。

2. コンパクト度を周長で評価する

人数を \(P\)、領域の周長を \(L\) とすると、コンパクト度は

\[ C=\frac{4\sqrt P}{L} \]

です。

同じグループについて考える間は \(P\) が固定なので、コンパクト度を高くすることは、周長 \(L\) を短くすることと同じです。

領域内で辺を共有しているマスの組数を \(E\) とすると、周長は

\[ L=4P-2E \]

とも書けます。各マスが最初に4辺を持ち、内部で隣接するマスの組が一つ増えるごとに境界辺が2本減るためです。

したがって、形状を一マスずつ作る場合は、すでに選んだ領域と多くの辺で接するマスを追加すると、周長を短くしやすくなります。この性質は、テンプレートを置けない場合の領域生成で使っています。

3. 人数ごとに低周長の形状を生成する

\(P\) は4から150までなので、それぞれについて連結形状を事前生成しました。

3.1 長方形に近い形を作る

基本となるのは、幅 \(w\) の長方形へ上から順にマスを詰め、最後の行だけ一部を残した形です。

例えば、最後の行を左端へ寄せるだけでなく、右端や中央にもずらします。さらに、長方形の上端と下端を段差状に削った形も生成します。

最初から細長い形を大量に持っても使いにくいため、その人数で得られる最小周長を \(L_{\min}\) として、

\[ L\le L_{\min}+2 \]

の形だけを残しました。

3.2 回転・反転と重複除去

生成した形について、90度回転、上下反転、左右反転を行います。その後、左上が \((0,0)\) になるように平行移動し、マスの列をソートしたものをキーとして重複を除きます。

これにより、一つの基本形から盤面の向きに応じた配置を探せます。

3.3 周長ごとの候補制限

形状は周長、縦横の差、高さ、幅の順で並べます。原則として各人数につき20形状までですが、最小周長の形が20個を超える場合は、それらをすべて残します。

配置探索でも周長の短い層から順に調べます。ある周長の形を一つでも置けた場合は、それより周長の長い層へは進みません。まず現在の利用料を落とさないことを優先しています。

4. ビットマスクで配置可能位置を列挙する

盤面サイズは \(50\times50\) なので、各行を u64 一つで表せます。

• grass_mask[x]: 行 \(x\) の芝生マス
• occupied_mask[x]: 行 \(x\) の使用中マス
• durable_contact_mask[x]: しばらく残るグループのマス

形状も行ごとのビットマスクとして保持します。

ある形状を \((x,y)\) へ置く場合、その行のビットマスクを \(y\) ビット左へずらし、芝生外または占有マスを表すビットマスクとのビット単位ANDが0かを見れば衝突判定できます。

実際には \(y\) を一つずつ試すのではなく、各形状・各 \(x\) について、置ける \(y\) を一つのビットマスクとしてまとめて求めます。得られたビットマスクから立っているビットを順に取り出すことで、配置可能なアンカーだけを列挙します。

5. 同じ形をどこへ置くか

同じ周長の形でも、空き地の中央へ置くか、池の横へ置くかで、その後の盤面はかなり変わります。

中央へ置くと空き地を二つに分けやすいため、基本的には、すでに使えない場所へ寄せるようにしました。

5.1 盤面端・池へ寄せる

候補領域の境界が、次のものへ何辺接しているかを数えます。

• 盤面外
• 池
• 現在使用中のマス

軽い候補評価では、おおよそ

\[ 25\times(接触辺数)+275\times(安定接触辺数) \]

を使います。

周長は同じ候補どうしを比べているため、この評価によって、壁や池へ沿い、まとまった空き地を残しやすい位置を選びます。

5.2 長く残るグループへ接触させる

既存グループへの接触は、そのグループがすぐ退去する場合にはあまり長持ちしません。

そこで、新しいグループの到着時刻を \(S_i\)、退去時刻を \(T_i\)、隣接する既存グループの退去時刻を \(T_j\) とし、接触が有効な割合を

\[ w_j= \frac{\min(T_j,T_i)-S_i}{T_i-S_i} \]

として \([0,1]\) に収めます。

\(T_j\ge T_i\) なら、新しいグループが帰るまで相手も残るので重みは1です。逆に相手が早く帰る場合は、その残存時間に応じて重みを小さくします。盤面外と池は常に残るため、重み1として扱います。

全候補へこの計算を行うと重いので、最初の候補選別では「新しいグループの滞在時間の4分の3以上残るか」という二値を使います。占有率45%以上かつ探索モードが Full または Reduced のときだけ、絞り込んだ候補を上の連続値で比較します。

5.3 混雑時は大きな空き連結成分を残す

占有率が85%以上の場合は、候補を置いた後の空き連結成分をBFSで調べます。

空きマスの総数を \(A\)、最大空き連結成分の大きさを \(M\) とすると、

\[ A-M \]

は、最大成分からこぼれた空きマスの総数です。この値が小さい候補を優先します。

空きマスが多くても、小さな成分へ分かれていると大人数グループには使えません。混雑時だけこの評価を行うことで、計算時間を抑えながら大きな空間を残します。

6. テンプレートが置けない場合のフォールバック

盤面が詰まると、低周長テンプレートが一つも入らないことがあります。その場合は、現在の空き方に合わせて任意の連結領域を作ります。

6.1 空き連結成分の列挙

まず、芝生かつ未占有のマスについて連結成分を列挙します。大きさが \(P\) 未満の成分は使えないので捨てます。

6.2 複数の開始点から領域を成長させる

残った連結成分から、複数の開始点を選びます。開始点は一種類に偏らないように、次のようなものを混ぜています。

• 盤面外、池、占有領域に多く接するマス
• 周囲に余裕がある内側のマス
• 各空き連結成分の代表点
• すでに選んだ開始点から遠いマス

各開始点から、連結性を保ったまま \(P\) マスまで領域を成長させます。ここでは、現在の領域に隣接する未選択マスをfrontierと呼びます。次に追加するマスは、現在領域との接触辺数を最優先にし、そのマスを加えたことで新たにfrontierへ入るマスの数や、開始点からの距離などで決めます。

大人数 \(P\ge101\) かつ空き連結成分が \(9P\) マス以上ある場合だけは、frontierを増やしにくい方向を優先します。十分に空間がある局面では、広がりながら進むより、境界を増やさず密に育てる方がよいと考えました。

6.3 周長を小さくする境界交換

領域を \(P\) マスまで成長させた後、領域の端から一マスを外し、別の隣接マスを追加する交換を試します。

外すマスが領域内で持つ隣接辺数を \(d_x\)、追加するマスが新しい領域と持つ隣接辺数を \(d_y\) とすると、内部隣接辺数の変化は

\[ \Delta E=d_y-d_x \]

です。連結性を壊さず、\(d_y>d_x\) となる交換を行えば周長を短くできます。

6.4 小さな空き成分を削って形を作る

空き連結成分の大きさが \(P+40\) 以下の場合は、開始点から育てる方法とは逆に、連結成分全体からマスを削る方法も試します。

削除しても残りが連結である端のマスを選び、\(P\) マスになるまで縮めます。到着人数と空き成分の大きさが近い場合は、すでにある空き形状を利用する方が自然な領域を作れることがあります。

最後に、生成した候補を周長、接触評価の順で比較します。

7. 収益密度による受入判定

配置できるグループをすべて受け入れると、価値の低いグループが長時間場所を占有し、後から来るグループを置けなくなります。

そこで、配置候補のコンパクト度を \(C_i\) として、収益密度を

\[ D_i=\frac{V_iC_i}{P_i(T_i-S_i)} \]

としました。

これは、利用料を占有面積と滞在時間で割った、1マス・1時間あたりの収益密度です。

7.1 過去200グループから閾値を決める

直近200到着の収益密度を保存し、そのパーセンタイルを受入閾値にします。履歴には受け入れたグループだけでなく、拒否した到着も含めます。配置を探索しなかった場合や配置が見つからなかった場合は、その人数のテンプレートで実現できる最高コンパクト度から計算した密度を保存します。

履歴が20件未満の場合と、占有率が30%未満の場合は選別しません。盤面に余裕があるうちは、将来のために場所を空けるより、現在の収益を取る方を優先します。

占有率が上がるほど、参照するパーセンタイルを高くします。現在の実装では、おおよそ次の範囲です。

占有率	使用するパーセンタイル
30%未満	選別しない
30%以上45%未満	10〜35%
45%以上85%未満	15〜56%
85%以上93%未満	60%
93%以上	80%

範囲がある部分は、直近需要に応じて切り替えます。

7.2 配置探索前の枝刈り

人数 \(P_i\) について、テンプレートで実現できる最高コンパクト度を \(C_i^{\max}\) とします。

\[ \frac{V_iC_i^{\max}}{P_i(T_i-S_i)} \]

が受入閾値を下回るなら、どこへ置いても基準を満たせません。この場合は配置探索を行わず、すぐ No にします。

実際の候補が見つかった後は、その候補の \(C_i\) でもう一度密度を計算し、最終的な受入判定を行います。

7.3 占有率と直近需要による調整

直近200到着について、要求面積と滞在時間の積

\[ P_i(T_i-S_i) \]

を記録します。これを面積×滞在時間と呼びます。履歴内で最も古い到着時刻から現在時刻までに要求された面積×滞在時間を、同じ期間に芝生全体が供給できる値で割り、最近の需要比として使います。

需要が高い場合は、占有率がまだ低い段階から受入閾値を上げます。需要が低い場合は、45〜85%の範囲でも閾値を緩めます。

7.4 池の形状による重み付け

池の境界辺数が300を超える盤面では、収益密度のパーセンタイルを計算するとき、各履歴を人数 \(P\) で重み付けします。

池が複雑な盤面では大人数グループを置ける場所が限られるため、小人数と同じ一票として扱うより、その占有面積を反映させる方がよいと考えました。手元の評価では、池の境界が単純な盤面には通常の重みなしパーセンタイルを使う組合せがよかったです。

7.5 終盤の閾値緩和

残り100グループに入ると、受入パーセンタイルを40%から0%へ線形に下げます。

最後まで空き地を温存しても、その空間を使う到着が残っていない可能性が高いためです。

8. 既存グループの再配置

テンプレートが置けず、フォールバックも見つからないか、得られた形のコンパクト度が低い場合は、既存グループを移動して場所を作ります。

通常配置が見つかっている場合でも、密度基準を満たさず拒否になったときは、移動費率が十分低ければ局所再配置をもう一度試します。

8.1 再配置の採算

移動する既存グループ \(j\) の移動費は

\[ M_j=\max(\operatorname{round}(V_jR),1) \]

です。

さらに、移動先のコンパクト度が過去の最小値を下回ると、そのグループの利用料も低下します。既存グループ \(j\) のそれまでの最小コンパクト度を \(C_j^{\min}\)、移動先のコンパクト度を \(C'_j\) とすると、再配置案の純利益は概ね

\[ \operatorname{round}(V_iC_i) -\sum_j M_j -\sum_j\left\{ \operatorname{round}(V_jC_j^{\min}) -\operatorname{round}\left(V_j\min(C_j^{\min},C'_j)\right) \right\} \]

として比較します。実装では各利用料を丸めてから差を取っています。

フォールバック配置がある場合は、そのまま受け入れた場合の利用料とも比較し、再配置後の純利益が上回る案だけを採用します。

8.2 少数のblockerを動かす局所再配置

新しいグループの理想形を盤面上へ仮置きし、そこに重なる既存グループをblockerとして集めます。

blockerが最大2グループで、移動費と予想損失が新しいグループの価値に見合う候補だけを残します。その後、blockerをいったん盤面から外し、新しいグループを置いてから、各blockerの移動先を探します。

移動先では、まず以前の最小コンパクト度を下回らないテンプレートを探します。到着グループの通常配置が基準よりかなり悪く、厳しい条件では移動先が見つからなかった場合に限り、フォールバックも使います。移動対象が到着グループより先、または同時に退去する場合に限って、以前の最小コンパクト度の80%以上まで許します。このとき生じる利用料低下は、再配置案の純利益から差し引きます。

8.3 空き地を分断するグループを動かす

移動費率が高いケースでは、多数のグループを動かす余裕がありません。その代わり、空き地を分断している一つのグループを探します。

各既存グループの周囲にある空き連結成分を調べ、そのグループを取り除いたときに、それらを合わせて新しいグループを置ける大きさになるかを見ます。

条件を満たすグループを一つだけ動かし、分断されていた空間へ到着グループを置いた後、動かしたグループの新しい置き場所を探します。

8.4 連鎖再配置と全体の詰め直し

移動費率が低い場合は、もう少し重い処理も試します。

連鎖再配置では、まず到着グループを空の作業盤面へ固定します。その後、利用中のグループを面積の大きい順に見て、元の場所がまだ空いていればそのまま戻し、すでに塞がれていれば別の配置先を探します。blockerを再帰的にたどるのではなく、前に配置したグループの影響を後続へ順に伝える形です。

また \(R\le0.010\) の場合は、現在利用中のグループと到着グループをまとめて、面積の大きい順などで空の盤面へ詰め直す案も試します。

どちらも組合せが急速に増えるため、到着位置、blocker数、移動先候補、探索時間を強く制限しています。

9. 移動費率 \(R\) による探索の切り替え

再配置は、移動費率に応じて次のように切り替えます。

\(R\)	主に試す処理
\(R\le0.010\)	連鎖再配置と全体の詰め直し
\(0.010<R\le0.050\)	連鎖再配置
\(0.050<R\le0.060\)	最大2グループの局所再配置
\(0.060<R\le0.100\)	一つの分断グループを動かす再配置
\(R>0.100\)	再配置しない（問題の制約外）

問題の制約は \(R\le0.100\) なので、上の最初の4行で実際の入力をすべて覆います。

また、再配置を開始するフォールバック品質の基準も変えます。\(R\le0.050\) では理論コンパクト度の80%未満、\(R>0.050\) では85%未満のときに再配置を検討します。どの再配置案も、最後は移動費と利用料低下を含む純利益で判定します。

10. 計算時間の管理

1000グループを2秒以内に処理する必要があるため、探索量は固定していません。

10.1 ターンごとの探索予算

内部の全体期限を 1995ms に設定しています。

各ターンでは、残りグループすべての出力時間と最後の 10ms を先に予約します。その後、残った時間を残りグループ数で割り、4倍まで前借りした値をそのターンの予算にします。ただし、一つのターンには最大 20ms しか使いません。

10.2 探索モード

そのターンに残された予算によって、次の4モードを切り替えます。

モード	処理
Full	詳細候補、フォールバック、再配置を使う
Reduced	詳細候補数と開始点数を減らす
Fast	最小周長テンプレートだけを調べる
Emergency	最初に見つかった合法配置を使う

重いループの途中でも定期的に時刻を確認し、期限に達した場合は、その時点までに完成している合法候補があれば返します。未完成の再配置案などは破棄します。

10.3 時間不足でも合法な出力を返す

探索時間を使い切っても、残りの入力を読み、各グループへ応答する必要があります。

そのため、残り時間が少ない場合はフォールバックや再配置を停止し、テンプレートの最小周長層だけを調べます。それも間に合わない場合は No を出力します。探索品質より、1000ターンすべてで合法な出力を行うことを優先します。

11. 1グループを処理する流れ

最終的な1ターンの処理は、概ね次の順です。

1. 到着したグループの \(S_i,T_i,P_i,V_i\) を読む
2. \(T_j<S_i\) を満たす退去済みグループを盤面から外す
3. 占有率、直近需要、密度履歴から受入閾値を計算する
4. 理論上の最高密度でも閾値未満なら、探索せず拒否する
5. 人数 \(P_i\) のテンプレートを周長の短い順に探索する
6. 必要に応じて、同じ周長の候補を接触寿命と空き連結成分で比較する
7. テンプレートが全滅した場合はフォールバック領域を生成する
8. 必要なら \(R\) に応じた再配置を試す
9. 再配置案の純利益とフォールバックの利用料を比較し、使う配置を決める
10. 選んだ配置のコンパクト度で収益密度を再計算する
11. 密度基準を満たさず、かつ \(R\le0.060\) なら、局所再配置をもう一度試す
12. 移動情報を出力し、その後 Yes と配置、または No を出力する
13. 今回の密度と面積×滞在時間を履歴へ追加する

12. まとめ

最終的な解法は、低周長形状を使う貪欲に、次の処理を加えたものです。

• ビットマスクによる配置可能位置の高速列挙
• 盤面端、池、長く残るグループへの接触評価
• 混雑時の最大空き連結成分の維持
• 空き連結成分から任意形状を作るフォールバック
• 収益密度の履歴を使った受入判定
• 移動費率に応じた局所再配置、分断解消、連鎖再配置
• 残り時間に応じた探索量の切り替え

基本的には、現在のグループをできるだけ周長の短い形で置きます。ただし、それだけでは後から来る大人数グループの場所がなくなるため、同じ周長なら空き地を分断しにくい場所を選びます。

それでも盤面が詰まった場合は、現在の空き方に合わせた形を直接作り、価値が十分高ければ既存グループを動かします。一方で、収益密度が低いグループは混雑度に応じて断ります。

「今の形をきれいにする」「次に使える空間を残す」「空間を誰に使うかを選ぶ」の三つを、別々の処理として組み合わせた解法になりました。