1. 全体方針

この問題では、各グループを単純に

空いているなら入れる

という方針ではあまり強くありません。

低価値なグループを長時間受け入れてしまうと、その後に現れる高価値なグループを置く場所がなくなります。また、空きマスの総数が十分でも、盤面が細かく分断されると大人数グループを置けません。

そこで、本解法では主に次の4点を考えます。

1. できるだけコンパクトな形で配置する
2. 将来使いやすい空き領域を残す
3. 将来需要を推定して受入可否を決める
4. 十分価値が高ければ既存グループを移動する

特に、単なる「現在の配置問題」ではなく、

空きマスの将来価値を考慮したオンライン資源配分問題

として扱うことを意識しました。

---

2. コンパクト度を内部隣接辺数で考える

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

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

です。

領域内で上下左右に隣接しているマスの組数を \(E\) とします。

各マスには4辺あるため最初は \(4P\) 辺ありますが、内部で隣接する1組につき境界から2辺消えるので、

\[ L=4P-2E \]

です。

したがって、

\[ C= \frac{4\sqrt P}{4P-2E}. \]

\(P\) は固定なので、これは

\[ E\text{ を最大化する} \]

ことと同値です。

つまり、

なるべく各マス同士を多く接触させればよい

という非常に扱いやすい形になります。

この性質は、形状生成・Greedy Grow・局所改善の全てで利用しています。

---

3. 高コンパクト形状のカタログ

毎ターン任意の \(P\) マス連結集合を探索するのは重いため、人数 \(P\) ごとに高品質な形状を生成します。

ただし全 \(P\) について最初に生成するのではなく、get_candidates(P) が最初に呼ばれた時点で生成し、その後キャッシュしています。

3.1 周長の短い形だけを見る

正方形に近い図形では

\[ h+w\simeq2\sqrt P \]

となります。

そこで

\[ H=\left\lceil2\sqrt P\right\rceil \]

として、実装では

\[ h+w\in{H,H+1,H+2} \]

の3 tier だけを調べます。

つまり、最初からコンパクト度が悪い細長い形状を大量に生成することはしません。

---

3.2 行区間として形状を列挙する

各行の領域を

\[ [l_i,r_i] \]

という1つの区間で表します。

例えば、

..####
.#####
######
.#####

のような形です。

長方形から左右を削る形で面積をちょうど \(P\) にし、凸状で穴のない形を多数生成します。

さらに、

• 上下反転
• 左右反転
• 90度回転
• それらの組合せ

を生成し、ハッシュで重複を除去します。

最終的にはコンパクト度の高い順に並べ、最大 MAX_SHAPES = 288 個程度を保持します。

---

4. 盤面上の配置候補もキャッシュする

生成した各形状について、

芝生だけを使って盤面のどこに置けるか

も調べます。

\(N=50\) なので1行は64 bit整数1個で表現できます。

各形状も行ごとの連続区間に変換しておき、bit 演算によって配置可能位置をまとめて探索します。

さらに各配置候補の占有領域も bit mask として保存します。

盤面全体は2500マスなので、

\[ \left\lceil\frac{2500}{64}\right\rceil=40 \]

ワードです。

そのため現在の占有領域との衝突は、概念的には

candidate_mask & occupied_mask

で高速に判定できます。

候補はコンパクト度・池や外周との接触度を考慮して絞り込み、人数ごとに最大 1649 個程度をキャッシュしています。

---

5. 配置場所の評価

同じ形状でも、どこに置くかは重要です。

実装では大きく

\[ \mathrm{Score}_{\mathrm{coarse}}=10^6C+w_sS \]

と、

\[ \mathrm{Score}_{\mathrm{fine}} =10^6C+w_qQ+w'_sS \]

の2段階で評価しています。

ここで、

• \(C\) : コンパクト度
• \(S\) : shelter
• \(Q\) : 配置後の空き盤面品質

です。

現在のコードでは概ね

\[ w_q=208351, \]

\[ w_s\simeq68.5,\qquad w'_s\simeq60.0 \]

です。

\(10^6C\) が非常に大きいため、基本的にはコンパクト度を最優先し、その中で将来の盤面を壊しにくい配置を選びます。

---

6. Shelter：壁際へ寄せる

空き領域の中央にグループを置くと、盤面を二つに分断しやすくなります。

そのため、

• 池
• 盤外
• 長期間残る既存グループ

へ接する配置を優先します。

新規グループの退去時刻を \(T_i\)、現在時刻を \(t\) とし、隣の既存グループ \(j\) の退去時刻を \(T_j\) とすると、その接触の重みは

\[ s_j= \min\left( 1,\frac{T_j-t}{T_i-t} \right) \]

としています。

したがって \(T_j\ge T_i\) ならほぼ完全な「壁」として扱えます。

池と盤外については重み1です。

この値を境界辺について足したものを shelter としています。

---

7. 将来使える大きな空間を残す

shelter だけでは、

大人数客が将来置けるか

までは十分に評価できません。

そこで上位候補については、配置後に残る空き正方形を評価します。

各空きマス \((i,j)\) に、

\[ D_{i,j} = \text{そのマスを右下とする最大空き正方形の一辺} \]

を持たせます。

通常の最大正方形 DP により、

\[ D_{i,j} = 1+\min \left( D_{i-1,j}, D_{i,j-1}, D_{i-1,j-1} \right) \]

と計算できます。

一辺 \(k\) 以上の正方形の個数を

\[ N_k = \#\{(i,j)\mid D_{i,j}\ge k\} \]

とし、

\[ Q= \sum_{k=2}^{13} w_k \frac{\log(1+N_k)} {\log(1+N^2)} \]

の形で評価します。

log を使うことで、「同じ大きさの正方形が大量にある」ことの価値を飽和させています。

また \(w_k\) は人数分布を意識した重みになっています。

配置候補ごとに \(50\times50\) 全体を再計算すると重いため、実際には変更の影響が伝播する場所だけ DP を差分更新します。

---

8. カタログで置けない場合

カタログ形状は高速ですが、池や既存客の間にできた歪な空き領域には弱いです。

そこで find_best() では、

1. カタログ探索
2. Window Packing
3. Greedy Grow

を順に組み合わせます。

ただし、カタログでほぼ理想コンパクト度に到達している場合は、重い fallback を省略します。

---

9. Window Packing

人数 \(P\) に対して、まず

\[ hw\ge P \]

を満たす正方形に近い長方形 \((h,w)\) を複数生成します。

特に

\[ hw-P \]

が小さいものを優先します。

二次元累積和を使って各長方形窓内の空きマス数を高速に数え、有望な窓だけを残します。

その後、窓内の中央付近から連結領域を成長させます。

追加候補は主に、

• 現在領域との接触辺数
• 窓の中心からの距離
• 周辺の空き具合

を基準に選びます。

特に、既に選んだ領域と3辺・4辺接しているマスは強く優先します。

---

10. Greedy Grow

Window Packing でも十分な候補が得られない場合、盤面上の複数の seed から直接 \(P\) マスの連結領域を成長させます。

新しいマスが現在領域に \(k\) 辺接すると、

\[ E\leftarrow E+k \]

となります。

したがって、なるべく \(k\) が大きいマスを選ぶことで周長を短くできます。

複数の seed から探索し、局所盤面が同じ場合の結果を memoization することで高速化しています。

---

11. 周長の局所改善

Window Packing や Greedy Grow で得た領域については、まず境界を軽量に修正します。

領域からマス \(x\) を1個外し、空きマス \(y\) を追加する

\[ R' = R-{x}+{y} \]

を考えます。

\(x\) の領域内次数を \(d_x\)、\(y\) の追加後の接触数を \(d_y\) とすれば、

\[ \Delta E=d_y-d_x. \]

したがって、

\[ d_y>d_x \]

となる交換でコンパクト度が改善します。

さらに \(P\ge41\) で時間に余裕がある場合は compact_region() による追加探索を行います。

改善 swap だけでなく、

• \(\Delta E=0\) の plateau move
• 少数の \(\Delta E=-1\) の escape move

も試します。

ただし常に連結性を壊さない交換だけを許可します。

---

12. 全員を受け入れない

この問題で特に重要だったのは受入判定です。

単純に「置ける客を全て入れる」と、将来価値の高い客に使うマスがなくなります。

そこで、

空きマスに時間方向の機会費用を設定する

ことにしました。

---

13. 到着データから価値分布をオンライン推定する

入力生成則から、価値 \(V\) は概ね

\[ V \simeq P,d^{0.9}2^X, \qquad d=T-S \]

という構造を持ちます。

そこで、

\[ q = \log_2V-\log_2P-0.9\log_2d \]

を観測します。

実装では到着済みグループから、この \(q\) の平均・分散を逐次更新します。

少数サンプル時に推定が暴れないように prior も加えています。

---

14. 滞在時間分布の推定

滞在時間は指数分布由来なので、スケールを \(\tau\) として推定します。

ただし時刻 \(S\) に到着したグループは

\[ d<100000-S \]

という打ち切りを受けます。

そのため単純な平均値ではなく、horizon \(H\) で打ち切られた指数分布の平均

\[ E[d\mid d<H] = \tau \left( 1-\frac{H/\tau}{e^{H/\tau}-1} \right) \]

を利用し、現在までの観測値と合う \(\tau\) を二分探索しています。

---

15. 1マス・1時間あたりの価値

あるグループの収益密度を

\[ \rho = \frac{VC}{Pd} \]

とします。

\[ V\simeq Pd^{0.9}2^q \]

なので、

\[ \rho = C,2^q,d^{-0.1}. \]

したがって、価格 \(p\) 以上の価値を持つ確率は

\[ \Pr(\rho\ge p) = \Pr\left( q\ge \log_2p +0.1\log_2d -\log_2C \right). \]

\(q\) を平均 \(\mu\)、標準偏差 \(\sigma\) の正規分布として近似すると、

\[ \Pr(\rho\ge p) = \frac12 \operatorname{erfc} \left( \frac{ \log_2p+0.1\log_2d-\log_2C-\mu }{ \sqrt2\sigma } \right). \]

これを離散化してテーブルに保持します。

---

16. 将来需要と供給から shadow price を求める

時間幅 \(W\) を考えます。

滞在時間 \(d\) の将来客がこの期間内で消費する期待 area-time は、

\[ A(d,W) = \begin{cases} dW-\dfrac12d^2 &(d\le W)\\ \dfrac12W^2 &(d>W). \end{cases} \]

としています。

残り到着率を \(\lambda\) とすると、価格 \(p\) 以上の客による需要を概念的に

\[ D(p,W) = \lambda E[P] E_d \left[ A(d,W)\Pr(\rho\ge p) \right] \]

と計算します。

一方、供給は

\[ S(W) = A_{\mathrm{eff}} W - \sum_{j \in \mathrm{active}} P_j \min(T_j-t, W) \]

ここで \(A_{\mathrm{eff}}\) は単純な芝生面積より少し小さく見積もった実効容量です。

そして

\[ D(p,W)\simeq S(W) \]

となる \(p\) を二分探索します。

これを空きマスの shadow price として使用します。

---

17. 複数 horizon の価格

短期客と長期客では価値が異なるため、現在のコードでは4種類の horizon を使います。

概ね

\[ \max(600,0.4\tau), \]

\[ \max(2000,1.5\tau), \]

\[ \max(7000,5\tau), \]

\[ \text{残り全期間} \]

です。

グループの滞在時間 \(d\) に応じて、対数時間軸上で価格を補間します。

最終的な機会費用は

\[ \mathrm{OppCost} = s(P),p(d),P,d \]

です。

ここで

\[ s(P) = \min\left( 1, \left(\frac{P}{E[P]}\right)^\gamma \right) \]

として、小人数客は隙間へ配置しやすい分だけ割引します。

また、非常に開けた盤面かつ移動コスト \(R\) が大きい場合には、この割引を滞在時間に応じて弱めています。

---

18. 直接受入判定

候補配置のコンパクト度を \(C\) とすれば、得られる収益は

\[ VC. \]

そこで、

\[ VC\ge\mathrm{OppCost} \]

を直接受入の基準にします。

必要なコンパクト度として書けば、

\[ C_{\mathrm{floor}} = \frac{\mathrm{OppCost}}{V}. \]

現在の実装では、この値を最初の find_best() の完全な下限制約にはしていません。

qualityFloor として高品質候補の選択・枝刈りに利用した後、

decisionComp >= compFloor

かつ

V * decisionComp >= opportunity_cost(...)

を満たすかを改めて判定しています。

この点は前回の説明よりこちらの方が正確です。

---

19. 既存客の再配置

直接配置できない場合や、配置できても理想コンパクト度から大きく劣る場合には make_room() を試します。

新規客の理想コンパクト度を \(C_{\mathrm{ideal}}\) とすれば、最大で得られる収益は

\[ V_iC_{\mathrm{ideal}}. \]

これが、

• 現在の直接配置による収益
• 受け入れない場合の機会費用

を十分上回る場合だけ、既存客を動かす意味があります。

---

20. Displacement Cost

既存グループ \(j\) の直接移動コストは、

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

しかし移動によってコンパクト度が悪化すると、利用料も低下します。

そこで過去に得られた配置コンパクト度を人数帯ごとのヒストグラムとして保存し、

\[ E[\Delta C_j] \]

を推定します。

移動対象を選ぶ段階では、

\[ D_j = M_j+V_jE[\Delta C_j] \]

を displacement cost として使用します。

実際に移動先を決めた後は、現在までの最小コンパクト度 \(C_j^{\min}\) と新しいコンパクト度 \(C'_j\) から

\[ V_j\max(0,C_j^{\min}-C'_j) \]

も予算に加えます。

---

21. Clearance 探索

まず、移動コストが予算内であり、

\[ P_j\le P_i \]

である既存グループを仮想的に盤面から取り除きます。

この仮想盤面で新規グループの高品質配置を探索します。

候補領域と実際に衝突するグループだけを blocker とし、通常は最大4グループに制限します。

新規グループを先に固定した後、blocker を残った盤面へ詰め直します。

移動順として、

• 大人数優先
• 逆順
• 現在の価値 \(V_jC_j^{\min}\) 順
• blocker が2個以下なら permutation

などを試します。

---

22. 連鎖再配置

blocker 自体の移動先が別の客に塞がれている場合は、さらに chain_relocate() を試します。

新規 X を置きたい
        ↓
A を動かす必要がある
        ↓
A の良い移動先に B がいる
        ↓
B も動かす

という連鎖です。

こちらは組合せ爆発しやすいため、

• blocker 数
• 移動予算
• 残り計算時間

を厳しく制限しています。

---

23. 再配置候補のランダム refinement

一度 clearance が成功しても、それが最良とは限りません。

そこで時間に余裕があれば、

• 一部 blocker を移動不可として固定する
• eviction penalty をランダムに揺らす
• 必要コンパクト度を少し上げる

といった操作で異なる候補を生成します。

最終的には、

\[ \mathrm{Net} = V_iC_i-\mathrm{relocation\ loss} \]

が最大となる案を採用します。

---

24. Tactical Move

通常配置そのものが見つからなかった場合には、時間に余裕があれば別系統の try_tactical_move() も試します。

こちらではカタログ上の高コンパクト候補を直接見て、そこに重なる blocker が十分少なく、移動費も新規客の利益に比べて小さい場合だけ再配置を試します。

現在のコードでは、

if (!yes && !place.ok && allowTactical)

の場合だけ実行されます。

したがって、

価格が少し足りず直接拒否しただけの客

に無条件で Tactical Move を使うわけではありません。

---

25. 高価値客ほど現在利益を優先する

既に受け入れた客の \(V\) の中央値を \(V_{\mathrm{med}}\) とし、

\[ f = \operatorname{clamp} \left( \frac{V_{\mathrm{med}}}{V_i}, f_{\min},f_{\max} \right) \]

を計算します。

この \(f\) を shelter や将来盤面品質に掛けます。

そのため、

\[ V_i\ll V_{\mathrm{med}} \]

なら将来盤面を壊さないことを強く評価し、

\[ V_i\gg V_{\mathrm{med}} \]

なら現在の高価値客を良い場所に置くことを優先します。

---

26. 計算時間制御

1000ターンを2秒で処理する必要があるため、各ターンで探索量を動的に変えます。

現在時刻を \(t_{\mathrm{cpu}}\)、残りターン数を \(K\) とすれば、

\[ b= \frac{T_{\mathrm{budget}}-t_{\mathrm{cpu}}}{K} \]

を残り1ターンあたりの計算予算とみなします。

現在のコードでは、

\[ T_{\mathrm{budget}}=1.90\ \mathrm{s} \]

で、さらに

\[ T_{\mathrm{hard}}=1.93\ \mathrm{s} \]

を超えた場合は重い処理を停止します。

時間に応じて、

• quality 評価候補数
• Window Packing の窓数
• Greedy Grow の seed 数
• Tactical Move
• Chain Relocation

などを段階的に削減します。

---

29. 1ターンの処理まとめ

最終的な処理は概ね以下です。

1. 退去済みグループを盤面から削除
2. 新しい \((S,T,P,V)\) を統計へ追加
3. 滞在時間・価値分布を更新
4. 将来需要から shadow price を計算
5. カタログから配置を探索
6. 必要なら Window Packing / Greedy Grow
7. 上位候補について将来盤面品質を評価
8. 必要なら領域をコンパクト化
9. \( VC\ge\mathrm{OppCost} \) なら直接受け入れる
10. 通常配置不能なら Tactical Move を検討
11. 受入不能、または理想形との差が大きければ Clearance を探索
12. 移動損失込みで利益が改善する場合のみ再配置
13. 残り時間に応じて探索量を調節

---

30. まとめ

この解法の中心となる考え方は、

空きマスを単なる0/1の空間ではなく、将来収益を生む有限資源として扱うこと

です。

配置については

\[ \text{compactness} + \text{shelter} + \text{future board quality} \]

を評価し、

受入判定については

\[ \text{current revenue} \quad\text{vs.}\quad \text{opportunity cost} \]

を比較します。

さらに高価値客については、

\[ \text{new revenue} - \text{movement cost} - \text{compactness loss} \]

を評価して既存客の再配置まで行います。

最終的には、

• 高コンパクト形状のカタログ
• Window Packing / Greedy Grow
• 空き正方形による将来盤面評価
• オンライン需要推定
• shadow price による受入判定
• blocker の Clearance / Chain Relocation
• 局所的なコンパクト化
• 残り時間に応じた探索量制御

を組み合わせた解法となっています。