Appearance
AHC014 - RectJoin
使用した主な手法:貪欲法 / 部分破壊と再構築(LNS) / 固定パターンによる評価 / 温度付き閾値受理
問題概要
長方形を作る際には、次の制約がある。
- 辺は座標軸に平行、または45度の斜め方向に限られる。
- 長方形の辺の途中に、すでに印がある点を含んではいけない。
- 過去に描いた長方形の辺と、正の長さで重なってはいけない(点で交わるのはよい)。
点
最終的に印が付いている点の集合を
盤面の外側ほど点の重みが大きい。ただし、大きな長方形を作ると辺が今後の操作を妨げることもある。重い点を増やすことと、後続の長方形を作りやすい盤面を保つことの両立が重要になる。
実装上のスコア
コードの State::sum は印のある点の重みの合計。State::score() は整数演算で得点を計算するため、公式の四捨五入とは異なり切り捨てになる。探索ではこの整数値を使い、最良解の更新は sum で判定している。
解法の概要
基本方針は、貪欲法で完成した解を作り、一部を壊して別の形に作り直すこと。この再構築を制限時間まで繰り返す。
- 初期解を作る:小さい長方形を優先する貪欲法を実行する。初期点が多い場合(
M >= 72)は、8種類の固定パターンを使う貪欲法も試し、最も重みの合計が大きい解を採用する。 - 一部を破壊する:既存の長方形からランダムに最大4個を選んで削除する。削除した長方形が追加した点を利用する、後続の長方形も連鎖的に削除する。
- 再構築する:残った盤面から貪欲法をもう一度実行する。評価方法をランダムに切り替えることで、毎回異なる作り直し方を試す。
- 採用または巻き戻し:得点が十分よければ変更を残し、そうでなければ破壊前に戻す。探索中に見つけた最良解は別途保存する。
このような部分破壊+再構築は、LNS(Large Neighborhood Search)と呼ばれる探索の一種である。長方形を1個だけ付け替えるより、大きく配置を変えられるのが利点。
| 項目 | この実装での設定 |
|---|---|
| 実行時間 | 4.80 秒(問題の制限は5秒) |
| 初期解 | 小面積貪欲。M >= 72 なら固定パターン8種も比較 |
| 破壊 | ランダムに最大4操作を選び、依存する操作も削除 |
| 破壊が大きすぎる場合 | 削除数が40以上ならその近傍をスキップ |
| 再構築 | 7種類の通常貪欲、または固定パターン貪欲 |
| 採用判定 | 温度に応じた閾値受理(固定閾値 0.8) |
実装の役割分担は次のとおり。
| 構造体・関数 | 役割 |
|---|---|
Input | 入力・全格子点の重みの総和を保持 |
Rect | 新しい点を先頭とした長方形4頂点を保持 |
State | 印・辺・最近傍表・操作列を管理 |
State::greedy() | 長方形を追加できなくなるまで貪欲構築 |
PatternMap / PatternScore | 目標とする小長方形の配置と成長しやすさの評価 |
remove_rects() | 操作の依存関係を保って部分削除 |
State::propose() / rollback() | 近傍生成と不採用時の復元 |
Solver | 初期解の比較・制限時間付き探索・出力 |
解法のエッセンス
長方形候補は「3点目」と8方向の最近傍から作る
既存の点を3つ選ぶ全探索はしない。代わりに、既存の点 p3 と、そこから直交する2方向にある最近傍の印 p2, p4 を使う。
長方形の4頂点を順に p1, p2, p3, p4 とすると、p1 が新たに置く点で、
となる。例えば p3=(2,2), p2=(4,2), p4=(2,4) なら、p1=(4,4)。
cpp
// State::push_from() より抜粋
int v = id(p3);
for (int d = 0; d < 8; ++d) {
int u2 = near[v][(d + 2) % 8];
int u4 = near[v][d];
if (u2 == -1 || u4 == -1) continue;
P p2 = point(u2), p4 = point(u4);
P p1{p2.first + p4.first - p3.first,
p2.second + p4.second - p3.second};
if (!inside(p1) || dot[id(p1)]) continue;
Rect r{{p1, p2, p3, p4}};
if (valid(r)) pq.push({r, evaluate(r, mode, rng, ps), ++serial});
}near[v][d] は、点 v から8方向のうち方向 d に見て、最も近い印の位置(なければ -1)。方向を2つ進めると90度回転するため、d と (d+2)%8 を組み合わせれば、軸平行と45度傾いた長方形の両方を生成できる。
ここでのポイントは、候補の長方形の形を push_from() で保証すること。後述の valid() は、その長方形を現在の盤面に置けるかどうかを確認する。
印と辺を分けて管理し、合法性を高速に判定する
盤面の状態は主に次の2つで持つ。
dot[v]:格子点vに印が付いているか。used[v][kind]:格子点vを始点とする単位線分が使われているか。方向は横・縦・2種類の斜めの計4種類。
長方形を構成する4辺を単位線分に分解し、すべての線分を調べる。
cpp
// State::valid() の辺チェックより抜粋
P p = {x1, y1};
while (p != P{x2, y2}) {
P q = {p.first + dx, p.second + dy};
if (p != r.p[k] && dot[id(p)]) return false;
if (used[min(id(p), id(q))][kind(p, q)]) return false;
p = q;
}これで、辺の途中に余計な印がある場合と、既存の辺に重複する場合を除外できる。線分の交差自体は、正の長さで重ならなければ許されるので、単位線分の使用状況を管理すれば十分である。
操作を追加すると set_edges(r, 1)、削除すると set_edges(r, 0) で使用状況を更新する。
8方向の最近傍表を差分更新する
毎回盤面全体から長方形を探すのは無駄が多い。そこで near を保持し、印を追加・削除した場所の周辺だけ更新する。
add_dot(p) では、点 p から各方向にある最初の印 q を見つけて、以下を行う。
near[p][d] = q:新しい点から見える最近傍を登録。near[q][(d+4)%8] = p:逆方向から見える最近傍を新しい点に差し替える。
remove_dot(p) では、p を挟んで両側にいた最近傍の印をつなぎ直す。削除のたびに rebuild_near() を呼ばずに済む。
優先度付きキューで貪欲に長方形を追加する
State::greedy() は priority_queue<Candidate> で追加候補を管理する。評価値の高い候補から取り出し、合法なら採用する。
cpp
// State::greedy() のメインループより抜粋
while (!pq.empty()) {
Rect r = pq.top().rect;
pq.pop();
if (!valid(r)) continue;
if (ps) ps->add_rect(r);
set_edges(r, 1);
add_dot(r.p[0]);
ans.push_back(r);
added.push_back(r);
push_from(r.p[0], mode, rng, pq, serial, ps.get());
for (int d = 0; d < 8; ++d) {
int u = near[id(r.p[0])][d];
if (u != -1) push_from(point(u), mode, rng, pq, serial, ps.get());
}
}印が1つ増えたときに候補が変わりうるのは、主にその点と8方向の最近傍の点。そこだけ候補を追加すればよい。
一方、キューに入れた候補が、その後の操作で置けなくなることもある。そのため取り出す際に valid(r) を再確認する。優先度はキューへの登録時に計算した値を使い、毎回再評価はしない。特に固定パターン評価では、現在の盤面に対して少し古い評価が残ることがあるが、実装を軽くするための割り切りになっている。
貪欲の評価方法を切り替える
最初の貪欲法では、基本的に小さな長方形を優先する。小さいものなら辺の占有が少なく、さらに印を追加できる余地を残しやすいと期待できる。
ただし、面積だけでは盤面外側の重い点を狙いにくい。再構築時には、evaluate() の mode を変えて複数の方針を試す。
mode | 評価値 | 狙い |
|---|---|---|
0, 1 | -area | 小さな長方形を優先 |
2 | w | 追加点の重みを優先 |
3 | 1000 * w / area | 重みと長方形の大きさを両立 |
4 | -area * rand(1,3) | 小面積優先にランダム性を追加 |
5 | w * rand(1,3) | 重み優先にランダム性を追加 |
6 | rand(1,3) * (1000*w) / area | 重み/面積のバランスにランダム性を追加 |
7 | 一様乱数 | 順序を大きく変える |
8 | PatternScore::gain() | 固定パターンに沿って育てる |
ここで w は追加点 p1 の重み、area はコード独自の「長方形の大きさ」の指標で、厳密な幾何学的面積ではない。軸平行では対角の座標差にそれぞれ +1 した積を用い、45度回転した場合も変換座標から類似の指標を求めている。
mode=0 は初期解の構築に使い、通常の再構築は mode=1..7 から選ぶ。複数の評価軸を混ぜることで、同じ部分を壊しても異なる配置を探索できる。
固定パターンで「次につながる盤面」を評価する
M >= 72 のときには、通常の貪欲法に加えて固定パターンを使う。
PatternMap は盤面上に、1×1の正方形と小さなひし形を多数配置した仮想的な目標図形の集合。中央から見た位置と偶奇条件で配置を切り替え、shift=0..7 の8通りを用意する。
この図形を必ず完成させるのではなく、その図形を今後作りやすい状態かを評価する。
PatternScore は、パターンごとに次の情報を管理する。
points[i]:パターンの4頂点のうち、印がある個数k。blocked[i]:パターンの辺のうち、すでに他の操作で使われている単位線分の数e。
cpp
// PatternScore::value()
static constexpr int partial[5] = {0, 2, 12, 22, 16};
return partial[k] - (k < 4 && e > 0 ? 30 : 0);頂点が3つそろう状態を高く評価し、4点未満で辺がふさがれている状態にはペナルティを与える。実際に partial[3] = 22 は partial[4] = 16 より高く、完成済みの図形よりも「あと1点で完成する余地」を重視した経験的な評価値になっている。さらにパターンの4頂点の最大重みを係数として掛け、外側へ成長しやすい配置を高く評価する。
新しい長方形を追加したときの変化量は、次のように計算する。
はパターン iの4頂点の最大重み。は追加点または追加辺によって影響を受けるパターンのみ。 は上の partialと辺の競合ペナルティからなる評価関数。
point_dep / edge_dep により影響するパターンだけを列挙し、全パターンを毎回なめないようにしている。
大切なのは、直近の追加点の得点だけでなく、次の長方形を作りやすい構造を評価していること。 初期解では8パターンをそれぞれ貪欲構築して得点を比較し、探索中も一定の頻度(M >= 72 かつ約1/6)で mode=8 を使う。
依存する操作も消す「部分破壊」
印の追加は後続の長方形に利用される。例えば R1 で追加した点を R2 が使い、R2 で追加した点を R3 が使っている場合、R1 だけを削除すると R2 以降の操作が成立しなくなる。
remove_rects() は、最大4操作をランダムに削除対象として選び、操作を追加順に走査する。各操作の既存3頂点(p[1]..p[3])に、すでに削除した操作が追加した点が含まれていたら、その操作も削除する。
cpp
// remove_rects() より抜粋
for (int i = 0; i < sz; ++i) {
const Rect& r = ans[i];
if (!del[i]) {
for (int j = 1; j < 4; ++j) {
P p = r.p[j];
if (removed[p.first * n + p.second]) del[i] = 1;
}
}
if (del[i]) {
P p = r.p[0];
removed[p.first * n + p.second] = 1;
if (++cnt >= 40) return false;
} else {
remain.push_back(r);
}
}追加順に1回走査すれば、依存関係が何段連鎖していても削除対象が伝播する。削除数が40以上になる場合は、変化が大きすぎる近傍としてスキップする。
再構築と巻き戻しで近傍探索する
State::propose() は、削除後の状態を作り、そこから貪欲法で長方形を追加できなくなるまで再構築する。穴を埋めるだけでなく、残った盤面全体から追加可能な候補を探す。
Undo には元の操作列、削除した長方形、再構築で追加した長方形を記録しておく。
cpp
struct Undo {
vector<Rect> old_ans, deleted, added;
};不採用なら rollback() で「今回追加した長方形を取り消す → 削除した長方形を戻す → 元の操作列を復元する」。dot、used、near を差分更新するため、毎回最初から盤面を構築し直す必要がない。
採用判定は通常の焼きなましではなく「閾値受理」
探索全体の構造は焼きなまし法と似ているが、このコードでは乱数による確率受理をしていない点に注意する。
cpp
ll new_score = state.score();
double progress = min(1.0, timer.time() / TIME_LIMIT);
double temp = START_TEMP + (END_TEMP - START_TEMP) * progress;
if (new_score > current_score ||
exp(double(new_score - current_score) / temp) > 0.8) {
current_score = new_score;
if (state.sum > best_sum) {
best_sum = state.sum;
best = state.ans;
}
} else {
state.rollback(undo);
}得点差を
となる。つまり、温度に応じた一定範囲の悪化は必ず採用し、それより大きい悪化は必ず棄却する方法である。
温度は 100000 → 10000 と線形に下げる。開始時は約22,314点、終了時は約2,231点の悪化までを許容する(いずれも実装内の score() 基準)。通常の焼きなましのような rng.rand01() < exp(Δ/T) とは異なるので、記事でも区別しておく。
探索中の最良解は best として保存し、最後は現在の解ではなく best を出力する。
この解法で押さえておきたいこと
この実装の中心は、難しい探索手法そのものよりも次の組み合わせにある。
- 長方形をすばやく列挙する:8方向の最近傍と
p1=p2+p4-p3を使う。 - 壊しても合法性を保つ:追加順を利用して依存する操作を連鎖削除し、差分更新と巻き戻しを行う。
- 再構築を多様化する:小面積・点の重み・ランダム性・将来の成長しやすさを組み合わせる。
特に、貪欲な構築を何度もやり直せる形にしてから、探索で改善するという構成は、他のAHCにも応用しやすい。