Skip to content

AHC014 - RectJoin ​

問題文(AtCoder) / コンテストページ

使用した主な手法:貪欲法 / 部分破壊と再構築(LNS) / 固定パターンによる評価 / 温度付き閾値受理

問題概要 ​

N×N の格子点に、最初から M 個の印が置かれている。既存の印がある3点と、まだ印がない1点を使って長方形を作り、新しい1点に印を追加する操作を繰り返す。盤面の大きさ N は31〜61の奇数で、初期の印は中央付近に配置される。

長方形を作る際には、次の制約がある。

  • 辺は座標軸に平行、または45度の斜め方向に限られる。
  • 長方形の辺の途中に、すでに印がある点を含んではいけない。
  • 過去に描いた長方形の辺と、正の長さで重なってはいけない(点で交わるのはよい)。

点 (x,y) の重みは、盤面の中心 c=(N−1)/2 からの距離で決まる。

w(x,y)=(x−c)2+(y−c)2+1

最終的に印が付いている点の集合を Q、全格子点の重みの総和を S とすると、得点は次のとおり。

round(106N2M∑(x,y)∈Qw(x,y)S)

盤面の外側ほど点の重みが大きい。ただし、大きな長方形を作ると辺が今後の操作を妨げることもある。重い点を増やすことと、後続の長方形を作りやすい盤面を保つことの両立が重要になる。

実装上のスコア

コードの State::sum は印のある点の重みの合計。State::score() は整数演算で得点を計算するため、公式の四捨五入とは異なり切り捨てになる。探索ではこの整数値を使い、最良解の更新は sum で判定している。

解法の概要 ​

基本方針は、貪欲法で完成した解を作り、一部を壊して別の形に作り直すこと。この再構築を制限時間まで繰り返す。

  1. 初期解を作る:小さい長方形を優先する貪欲法を実行する。初期点が多い場合(M >= 72)は、8種類の固定パターンを使う貪欲法も試し、最も重みの合計が大きい解を採用する。
  2. 一部を破壊する:既存の長方形からランダムに最大4個を選んで削除する。削除した長方形が追加した点を利用する、後続の長方形も連鎖的に削除する。
  3. 再構築する:残った盤面から貪欲法をもう一度実行する。評価方法をランダムに切り替えることで、毎回異なる作り直し方を試す。
  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 を使う。

既存の3点から新しい点を求める模式図

長方形の4頂点を順に p1, p2, p3, p4 とすると、p1 が新たに置く点で、

p1=p2+p4−p3

となる。例えば 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小さな長方形を優先
2w追加点の重みを優先
31000 * w / area重みと長方形の大きさを両立
4-area * rand(1,3)小面積優先にランダム性を追加
5w * rand(1,3)重み優先にランダム性を追加
6rand(1,3) * (1000*w) / area重み/面積のバランスにランダム性を追加
7一様乱数順序を大きく変える
8PatternScore::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頂点の最大重みを係数として掛け、外側へ成長しやすい配置を高く評価する。

新しい長方形を追加したときの変化量は、次のように計算する。

gain(r)=∑i∈A(r)Wi(f(ki+Δki,ei+Δei)−f(ki,ei))
  • Wi はパターン i の4頂点の最大重み。
  • A(r) は追加点または追加辺によって影響を受けるパターンのみ。
  • f は上の 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);
}

得点差を Δ=new_score−current_score とすると、採用条件は

exp⁡(Δ/T)>0.8⟺Δ>Tlog⁡(0.8)≈−0.22314T

となる。つまり、温度に応じた一定範囲の悪化は必ず採用し、それより大きい悪化は必ず棄却する方法である。

温度は 100000 → 10000 と線形に下げる。開始時は約22,314点、終了時は約2,231点の悪化までを許容する(いずれも実装内の score() 基準)。通常の焼きなましのような rng.rand01() < exp(Δ/T) とは異なるので、記事でも区別しておく。

探索中の最良解は best として保存し、最後は現在の解ではなく best を出力する。

この解法で押さえておきたいこと ​

この実装の中心は、難しい探索手法そのものよりも次の組み合わせにある。

  1. 長方形をすばやく列挙する:8方向の最近傍と p1=p2+p4-p3 を使う。
  2. 壊しても合法性を保つ:追加順を利用して依存する操作を連鎖削除し、差分更新と巻き戻しを行う。
  3. 再構築を多様化する:小面積・点の重み・ランダム性・将来の成長しやすさを組み合わせる。

特に、貪欲な構築を何度もやり直せる形にしてから、探索で改善するという構成は、他のAHCにも応用しやすい。