A - Castle Renovation with Linked Doors 解説
by 
Kyo25
解法と考察など
このコンテストを振り返るためにChatGPTで解説を作成しました。今回の解説を執筆してくださったモデルはGPT-5.6 Solです。それではご覧ください。
ランダム全域木上のグレイコード構築 + 厳密 BFS + 焼きなまし
概要
勇者が入口から玉座へ到達するための最小行動回数を \(T\) とします。得点は \(T\) の単調増加関数なので、本解法では \(T\) を直接最大化します。
解法全体は次の流れです。
- 空きマスからなるグラフの全域木をランダムに生成する。
- 入口から玉座までの木上のパスを「幹」とする。
- 幹から伸びる枝に \(10\) 個のスイッチを配置する。
- \(19\) 枚の扉でグレイコード型の状態遷移を作る。
- 残りの扉で、元のグラフに存在するショートカットを塞ぐ。
- 全候補の真の \(T\) を状態数 \(400\times 2^{10}=409600\) の BFS で厳密に評価する。
- 最後に、余剰扉だけを焼きなましで改善する。
この解法の中心は、探索だけに任せるのではなく、まず全域木上で強い構造を作り、その構造を壊す非木辺だけを後から最適化する点です。
1. 盤面をグラフとして見る
空きマスを頂点、隣接する空きマス間の移動を辺とする無向グラフを考えます。
このグラフから全域木を一つ選ぶと、入口 \((0,0)\) から玉座 \((19,19)\) までの経路は一意になります。この経路を
\[ P=(p_0,p_1,\ldots,p_L) \]
とし、以降「幹」と呼びます。ここで \(p_0\) が入口、\(p_L\) が玉座です。
幹以外の頂点は、幹上のいずれかの頂点に接続された部分木に属します。幹上の位置 \(m\) に接続された部分木について、幹から最も遠い葉までの距離を \(d\) とし、その葉をスイッチの設置候補にします。
コードでは一つの枝候補を次の情報で管理しています。
struct Branch {
int spine_idx; // 幹との接続位置
int depth; // 幹から葉までの距離
int leaf; // スイッチを置く葉
int root; // 幹に隣接する枝側の頂点
};
スイッチ \(k\) を置く枝について、幹との接続位置を \(m_k\)、枝の深さを \(d_k\) とします。選択する枝は
\[ m_0\le m_1\le\cdots\le m_9 \]
となるように並べます。
2. 扉の開閉条件
スイッチ \(k\) の状態を \(b_k\in\{0,1\}\) とします。
扉番号 \(g\) に対し、コード中の開閉条件は
\[ \text{door }g\text{ is open} \iff b_{\lfloor g/2\rfloor}=g\bmod 2 \]
です。
したがって、同じビット \(b_k\) に対応する二枚の扉は相補的に開閉します。
- 偶数扉 \(2k\) は、\(b_k=0\) のとき開く。
- 奇数扉 \(2k+1\) は、\(b_k=1\) のとき開く。
コードでは、この判定を全ての状態について事前計算しています。
open_table[mask][g]
= (((mask >> (g >> 1)) & 1) == (g & 1));
3. 一ビット分の分岐装置
スイッチ \(k+1\) の枝が幹上の頂点 \(p_{m_{k+1}}\) に接続しているとします。この位置に次の二枚の扉を置きます。
- 枝へ入る辺に奇数扉 \(2k+1\) を置く。
- 幹を先へ進む辺に偶数扉 \(2k\) を置く。
構造を図で表すと次のようになります。
\[ \begin{aligned} &\text{switch }k+1\\ &\updownarrow\;\text{door }2k+1\\ &p_{m_{k+1}} \overset{\text{door }2k}{\longleftrightarrow} p_{m_{k+1}+1} \longleftrightarrow\cdots\longleftrightarrow \text{goal} \end{aligned} \]
この装置の状態は次の二通りです。
- \(b_k=0\) のとき、枝側は閉じ、幹の先は開く。
- \(b_k=1\) のとき、枝側は開き、幹の先は閉じる。
よって、スイッチ \(k+1\) を押すには \(b_k=1\) が必要です。しかし、その状態では幹を先へ進めません。スイッチ \(k+1\) を押した後、先へ進むためには以前の場所へ戻り、\(b_k\) を再び \(0\) に戻す必要があります。
スイッチ \(0\) の枝には入口用の扉を置かず、常に進入可能にします。また、玉座直前の辺には扉 \(19\) を置き、\(b_9=1\) のときだけ玉座へ入れるようにします。
基本構築に必要な扉は次の \(19\) 枚です。
- スイッチ \(1,2,\ldots,9\) の枝に置く奇数扉が \(9\) 枚。
- それぞれの分岐位置から幹を先へ進む辺に置く偶数扉が \(9\) 枚。
- 玉座直前に置く扉 \(19\) が \(1\) 枚。
コードでは、この \(19\) 枚を後段の局所探索から保護しています。
const int PROTECTED = 19;
4. グレイコード型のスイッチ列
4.1 押されるスイッチの順序
上記の構築では、余計な操作を除くと、勇者が押すスイッチ番号は
\[ 0,1,0,2,0,1,0,3,0,1,0,2,\ldots \]
となります。
時刻 \(t=1,2,\ldots,2^K-1\) に押すスイッチ番号を \(a_t\) とすると、
\[ a_t=\operatorname{ctz}(t) \]
です。ここで \(\operatorname{ctz}(t)\) は、\(t\) の二進表現の末尾に並ぶ \(0\) の個数です。
この列は、二進反射グレイコード
\[ g(t)=t\oplus(t\gg1) \]
において、\(g(t-1)\) から \(g(t)\) へ移る際に反転するビットの列と一致します。
列を \(S_K\) と書くと、再帰的に
\[ S_1=(0), \\ S_K=(S_{K-1},K-1,S_{K-1}) \]
となります。
今回の \(K=10\) では、スイッチを押す回数は
\[ 2^{10}-1=1023 \]
です。
4.2 なぜこの順序になるか
スイッチ \(k+1\) の枝へ入るには \(b_k=1\) が必要です。一方、その位置まで幹を進むには、下位ビットに対応する偶数扉が開いている必要があります。そのため、基本的には
\[ b_0=b_1=\cdots=b_{k-1}=0, \\ b_k=1 \]
という状態を作ってから、スイッチ \(k+1\) の枝へ入ります。
スイッチ \(k+1\) を押した後も、幹を先へ進むためには下位ビットを再び全て \(0\) に戻す必要があります。
つまり、
- 下位ビットを一巡させる。
- ビット \(k\) を反転する。
- 下位ビットをもう一巡させる。
という再帰構造が生じます。これが \(S_K=(S_{K-1},K-1,S_{K-1})\) となる理由です。
5. 全域木上での行動回数
全域木上では経路が一意なので、行動回数をほぼ解析的に計算できます。
スイッチ \(k\) の枝について、接続位置を \(m_k\)、深さを \(d_k\) とします。
枝部分の係数を \(w_k^{(d)}\)、幹部分の係数を \(w_k^{(m)}\) とすると、全域木上での最小行動回数は
\[ T_{\mathrm{tree}} =(2^K-1)+L +\sum_{k=0}^{K-1} \left( w_k^{(d)}d_k+w_k^{(m)}m_k \right) \]
と書けます。
各項の意味は次の通りです。
- \(2^K-1\) はスイッチを押す回数。
- \(L\) は入口から玉座まで幹を一度進む分。
- \(w_k^{(d)}d_k\) はスイッチ \(k\) の枝を往復する距離。
- \(w_k^{(m)}m_k\) は異なる枝の間を幹上で移動する距離への寄与。
コード中では、\(w_k^{(d)}\) を depthW[k]、\(w_k^{(m)}\) を spineCoeff[k] に保存しています。係数は、列 \(a_t=\operatorname{ctz}(t)\) を実際に走査して求めています。
for (int step = 1; step < FULL; step++) {
int nxt = __builtin_ctz((unsigned)step);
// 直前の枝から nxt の枝への移動を係数へ加算する
}
\(K=10\) のとき、係数は次のようになります。
- \(k=0\) では、\(w_0^{(d)}=1024\)、\(w_0^{(m)}=-1022\)。
- \(k=1\) では、\(w_1^{(d)}=512\)、\(w_1^{(m)}=512\)。
- \(k=2\) では、\(w_2^{(d)}=256\)、\(w_2^{(m)}=256\)。
- \(k=3\) では、\(w_3^{(d)}=128\)、\(w_3^{(m)}=128\)。
- \(k=4\) では、\(w_4^{(d)}=64\)、\(w_4^{(m)}=64\)。
- \(k=5\) では、\(w_5^{(d)}=32\)、\(w_5^{(m)}=32\)。
- \(k=6\) では、\(w_6^{(d)}=16\)、\(w_6^{(m)}=16\)。
- \(k=7\) では、\(w_7^{(d)}=8\)、\(w_7^{(m)}=8\)。
- \(k=8\) では、\(w_8^{(d)}=4\)、\(w_8^{(m)}=4\)。
- \(k=9\) では、\(w_9^{(d)}=2\)、\(w_9^{(m)}=2\)。
この係数から、次の性質が分かります。
- 小さい番号のスイッチほど訪問回数が多いため、深い枝へ置く価値が高い。
- \(w_0^{(m)}<0\) なので、スイッチ \(0\) は幹の入口側に置くほど有利である。
- \(k\ge1\) では \(w_k^{(m)}>0\) なので、大きい番号のスイッチは幹の奥側に置くほど有利である。
候補木の比較には、全候補で共通な \(2^K-1\) を省略した
\[ L+\sum_{k=0}^{K-1} \left( w_k^{(d)}d_k+w_k^{(m)}m_k \right) \]
を用いています。
実装は candidate_score() に対応します。
long long candidate_score(const vector<int>& path,
const vector<Branch>& sel) {
long long s = path.size();
for (int k = 0; k < 10; k++) {
s += depthW[k] * sel[k].depth
+ spineCoeff[k] * sel[k].spine_idx;
}
return s;
}
path.size() は \(L+1\) ですが、この \(1\) の差は候補の順位に影響しません。
6. 動的計画法による枝選択
幹上の各位置 \(m\) について、その位置から伸びる枝候補を深さ順に並べます。同じ位置へ同じ番号のスイッチを置くなら、最も深い枝が常に有利なので、通常は最深の一枝だけを考えれば十分です。
DP の状態を
\[ \mathrm{dp}[k][m] \]
とし、次の意味を持たせます。
幹の位置 \(0,1,\ldots,m-1\) を処理し、スイッチ \(0,1,\ldots,k-1\) の枝を選んだときの最大評価値。
各位置 \(m\) では次の遷移を行います。
- 位置 \(m\) を使わず、\(\mathrm{dp}[k][m+1]\) へ進む。
- 位置 \(m\) の最深枝をスイッチ \(k\) に割り当て、\(\mathrm{dp}[k+1][m+1]\) へ進む。
二番目の遷移で加える値は
\[ w_k^{(d)}d+w_k^{(m)}m \]
です。これにより、\(m_0\le m_1\le\cdots\le m_9\) を保ちながら、全域木上の評価を最大化できます。
例外として、スイッチ \(0\) とスイッチ \(1\) に限り、同じ幹位置から伸びる異なる二本の枝を同時に使う遷移も試しています。
if (k == 0 && br_idx[m].size() >= 2) {
// switch 0, 1 を同じ幹位置の 2 本の枝へ置く
}
低位ビットは訪問頻度が高いため、同じ位置に深い枝が二本ある場合、この例外遷移が有効になることがあります。
7. 全域木の生成
制限時間の前半では、多数の全域木を生成します。形の異なる木を得るため、次の三方式を混ぜました。
7.1 ランダム DFS 木
隣接頂点をランダム順に探索して DFS 木を作ります。細長い幹や深い枝が生じやすい方式です。
7.2 ランダム Kruskal 木
各辺へ乱数の重みを付け、Kruskal 法で全域木を作ります。DFS 木とは異なる形の候補を得られます。
7.3 玉座から遠ざかる DFS 木
次に進む頂点を選ぶ際、玉座 \((19,19)\) からのマンハッタン距離が大きい方向をやや優先します。入口から玉座までの木上距離 \(L\) が長い候補を狙うための方式です。
一つの全域木に対して、次の処理を行います。
- 幹 \(P\) を抽出する。
- 幹から伸びる枝候補を列挙する。
- DP で \(10\) 本の枝を選ぶ。
- \(T_{\mathrm{tree}}\) に対応する理論評価値を計算する。
理論評価値が高い上位 \(14\) 個の木だけを保持します。
ただし、この評価は「盤面が全域木そのものだった場合」の値です。元のグラフに残る非木辺によるショートカットは考慮していないため、最終選択には後述する厳密 BFS を使います。
8. 非木辺のショートカットを塞ぐ
全域木上では狙ったグレイコード構築が成立します。しかし、元の盤面には木へ採用しなかった辺が残っています。これらの非木辺を自由に通れると、勇者が枝の往復や幹上の扉を迂回できます。
基本構築で \(19\) 枚の扉を使用するため、残り最大 \(31\) 枚を非木辺へ置きます。
8.1 木距離による優先順位
非木辺 \((u,v)\) が存在すると、全域木上では長い距離を移動する必要があった \(u\) と \(v\) の間を一手で移動できます。
そこで、
\[ \operatorname{dist}_{\mathrm{tree}}(u,v) \]
が大きい非木辺ほど危険なショートカットとみなし、優先的に扉を置きます。
back_edges.push_back({tree_dist(a, b), {a, b}});
sort(back_edges.rbegin(), back_edges.rend());
8.2 余剰扉の型
余剰扉には主に扉 \(19,17,15\) などの大きい奇数型を使います。
奇数扉は初期状態で閉じています。また、高位ビットは反転頻度が低いため、長い時間同じ開閉状態を保ちます。この性質により、危険なショートカットを長時間閉じたままにできることがあります。
ただし、最適な扉型は非木辺の位置と状態遷移に依存します。そこで、木距離や危険度順位に応じて型を割り当てる複数のパターンを作り、それぞれの真の \(T\) を BFS で比較します。
上位の木候補ほど多くのパターンを試します。
int maxPattern = (idx < 5 ? 5 : 3);
9. 厳密評価 BFS
9.1 状態
勇者の状態は、現在位置 \(c\) とスイッチ状態 \(\mu\) の組
\[ (c,\mu) \]
で一意に決まります。ここで \(0\le c<400\)、\(0\le\mu<2^{10}\) です。
コードでは、二つを
\[ \operatorname{id}(c,\mu)=c\cdot2^{10}+\mu \]
として一次元整数へ圧縮しています。
static constexpr int FULL = 1 << K;
static constexpr int STATES = 400 * FULL;
初期状態は入口かつ全ビットが \(0\) なので、状態番号も \(0\) です。玉座のマスに初めて到達した状態の BFS 距離が、求める最小行動回数 \(T\) です。
9.2 遷移
各状態から行える操作は次の二種類です。
- 開いている辺を通って隣接マスへ移動する。
- 現在のマスにスイッチ \(s\) があれば、ビット \(s\) を反転する。
スイッチ操作後の状態は
\[ \mu' = \mu\oplus 2^s \]
です。実装では状態番号へ同じ排他的論理和を行っています。
int nx = cur ^ (1 << s);
扉のない辺には番兵値 OPEN = 20 を割り当て、常に通行可能として扱います。
9.3 BFS の高速化
焼きなまし中に BFS を何度も実行するため、次の高速化を入れています。
- 状態を一次元整数へ圧縮する。
vectorではなく固定長配列のキューを使う。- 隣接マスへ移動したときの状態番号差分を事前計算する。
- 各辺の扉番号を隣接配列へ直接保存する。
- 扉を変更したとき、その辺の情報だけを書き換える。
- 訪問配列を毎回初期化せず、探索世代を表す
vis_tokenを使う。
訪問配列の世代番号方式は次のようになっています。
++vis_token;
vis[nx] = vis_token;
一回の BFS の最悪計算量は
\[ O(N^2 2^K) \]
です。今回の固定値では状態数は約 \(41\) 万です。
10. 理論評価と厳密評価の二段階化
制限時間のうち約 \(1.08\) 秒を、全域木の生成と理論評価に使います。
const double TREE_TIME = 1.08;
多数の木を全て BFS で評価すると重いため、まず \(T_{\mathrm{tree}}\) に対応する安価な評価値で候補を絞ります。その後、上位候補だけについて余剰扉の配置パターンを構築し、BFS で真の \(T\) を計算します。
この二段階化には次の役割分担があります。
- 理論評価は、多数の全域木を高速に順位付けする。
- 厳密 BFS は、非木辺を含む実際の盤面で候補を比較する。
木上の評価が高くても、少数の非木辺で大きく短絡される候補があります。逆に、理論値が少し低くても、危険な非木辺を少数の扉で塞げる候補は真の \(T\) が高くなります。
このため、最終的な候補選択には必ず厳密 BFS を用います。
11. 余剰扉の焼きなまし
後半約 \(0.86\) 秒では、最良候補の基本扉 \(19\) 枚を固定し、余剰扉だけを焼きなましで改善します。
評価値には、BFS で求めた真の \(T\) をそのまま使います。
11.1 近傍
次の四種類の近傍を使います。
- 追加
- 未使用の非木辺へ扉を一枚追加する。
- 削除
- 余剰扉を一枚削除する。
- 型変更
- 余剰扉の位置を保ち、扉番号だけを変更する。
- 移動
- 余剰扉を別の非木辺へ移す。
基本構築に使用した木の辺は変更せず、主にショートカットとなる非木辺だけを探索対象にします。
新しい配置で玉座へ到達不能になった場合、calcT() は \(0\) を返すため、その遷移を棄却します。
11.2 受理確率
現在の評価値を \(T_{\mathrm{cur}}\)、近傍適用後を \(T_{\mathrm{next}}\)、温度を \(\tau\) とします。
悪化遷移は
\[ \exp\left( \frac{T_{\mathrm{next}}-T_{\mathrm{cur}}}{\tau} \right) \]
の確率で受理します。
温度は時間に対して幾何的に下げ、開始温度を \(6.0\)、終了温度を \(0.02\) としています。
double temp0 = 6.0;
double temp1 = 0.02;
12. 全体の処理手順
最終的なアルゴリズムは次の通りです。
- 入力から空きマスグラフを構築する。
- 約 \(1.08\) 秒間、ランダム全域木を生成する。
- 各木から入口―玉座間の幹 \(P\) を抽出する。
- 幹から伸びる枝候補を列挙する。
- DP でスイッチ用の \(10\) 本の枝を選ぶ。
- 理論評価上位 \(14\) 個の木を保持する。
- 各候補に基本扉 \(19\) 枚を配置する。
- 非木辺へ余剰扉を置く複数パターンを生成する。
- \(409600\) 状態の BFS で各候補の真の \(T\) を比較する。
- 最良候補の余剰扉を焼きなましで改善する。
- 探索中に得た最良配置を出力する。
13. まとめ
本解法では、問題を最初から \(400\times2^{10}\) 状態の一般グラフとして最適化するのではなく、まず全域木上へ制限して解析可能な構造を作りました。
重要だった点は次の通りです。
- 相補的に開閉する扉を使い、グレイコード型のスイッチ列を強制した。
- 全域木上の行動回数 \(T_{\mathrm{tree}}\) を、枝の深さ \(d_k\) と幹上の位置 \(m_k\) の一次式として評価した。
- DP により、係数に合った \(10\) 本の枝を選択した。
- ランダム全域木を多数生成し、幹と枝の形そのものを探索した。
- 非木辺によるショートカットだけを余剰扉で塞いだ。
- 最後は厳密 BFS で真の \(T\) を評価し、余剰扉を焼きなましで改善した。
「解析しやすい木上で強い構築を作る」「元のグラフとの差分だけを探索する」「最後は厳密評価する」という三段階に分けたことが、この提出の基本方針です。
いかがでしたでしょうか。私はコードや解説を考えたり理解したりすることはできませんが、ストーリーやヴィジュアライザーによってコンテストを楽しむことができました。また、よさげな解答や解法をChatGPTによって皆さんと共有できたことは素晴らしいと感じます。ではまたAtCoder Heuristic Contestの解説でお会いしましょう。さようなら！
ソースコード
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
static constexpr int N = 20;
static constexpr int M = 50;
static constexpr int K = 10;
static constexpr int FULL = 1 << K;
static constexpr int STATES = 400 * FULL;
static constexpr int OPEN = 20;
char cell_[N][N];
int door_h[N][N], door_v[N][N], switch_map_[N][N];
int door_h_idx[N][N], door_v_idx[N][N], switch_idx_[N][N];
struct Door { int d, i, j, g; };
struct SwOut { int i, j, s; };
struct Branch {
int spine_idx;
int depth;
int leaf;
int root;
};
struct TreeCand {
long long score = LLONG_MIN;
vector<int> path;
vector<Branch> branches;
array<vector<int>, 400> tree_adj;
};
vector<Door> current_doors;
vector<pair<int,int>> current_switches;
vector<pair<int,int>> valid_h_doors, valid_v_doors;
vector<int> valid_cells;
uint32_t vis[STATES];
int dist_arr[STATES];
int que[STATES + 8];
uint32_t vis_token = 0;
bool open_table[FULL][21];
int adjN[400];
int adjDelta[400][4];
int8_t adjDoor[400][4];
int8_t swFlat[400];
int rr[400], cc[400];
const int di4[4] = {-1, 1, 0, 0};
const int dj4[4] = {0, 0, -1, 1};
struct FastRng {
using result_type = uint32_t;
uint64_t x;
explicit FastRng(uint64_t seed=88172645463325252ULL) : x(seed) {}
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return UINT32_MAX; }
inline result_type operator()() { return next32(); }
inline uint32_t next32() {
x ^= x << 7;
x ^= x >> 9;
return (uint32_t)(x & 0xffffffffu);
}
inline int randint(int n) { return (int)(next32() % (uint32_t)n); }
inline double real01() { return (next32() + 0.5) * (1.0 / 4294967296.0); }
};
static inline int cellId(int i, int j) { return i * N + j; }
static inline int edgeDir(int a, int b) { return (rr[a] == rr[b]) ? 1 : 0; }
static inline int edgeI(int a, int b) { return min(rr[a], rr[b]); }
static inline int edgeJ(int a, int b) { return min(cc[a], cc[b]); }
void init_tables() {
for (int id = 0; id < 400; id++) { rr[id] = id / N; cc[id] = id % N; }
for (int mask = 0; mask < FULL; mask++) {
for (int g = 0; g < 20; g++) open_table[mask][g] = (((mask >> (g >> 1)) & 1) == (g & 1));
open_table[mask][OPEN] = true;
}
}
void buildAdj() {
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
int c = cellId(i, j);
swFlat[c] = switch_map_[i][j];
if (cell_[i][j] == '#') { adjN[c] = 0; continue; }
int n = 0;
if (i + 1 < N && cell_[i + 1][j] == '.') {
adjDelta[c][n] = FULL * N;
adjDoor[c][n++] = (door_h[i][j] < 0 ? OPEN : door_h[i][j]);
}
if (i - 1 >= 0 && cell_[i - 1][j] == '.') {
adjDelta[c][n] = -FULL * N;
adjDoor[c][n++] = (door_h[i - 1][j] < 0 ? OPEN : door_h[i - 1][j]);
}
if (j + 1 < N && cell_[i][j + 1] == '.') {
adjDelta[c][n] = FULL;
adjDoor[c][n++] = (door_v[i][j] < 0 ? OPEN : door_v[i][j]);
}
if (j - 1 >= 0 && cell_[i][j - 1] == '.') {
adjDelta[c][n] = -FULL;
adjDoor[c][n++] = (door_v[i][j - 1] < 0 ? OPEN : door_v[i][j - 1]);
}
adjN[c] = n;
}
}
void setEdgeDoor(int d, int i, int j, int g) {
int code = (g < 0 ? OPEN : g);
int u = cellId(i, j);
int v = (d == 0 ? cellId(i + 1, j) : cellId(i, j + 1));
int duv = (v - u) * FULL;
int dvu = -duv;
for (int k = 0; k < adjN[u]; k++) if (adjDelta[u][k] == duv) { adjDoor[u][k] = code; break; }
for (int k = 0; k < adjN[v]; k++) if (adjDelta[v][k] == dvu) { adjDoor[v][k] = code; break; }
}
int calcT() {
++vis_token;
if (vis_token == 0) { memset(vis, 0, sizeof(vis)); vis_token = 1; }
int head = 0, tail = 0;
que[tail++] = 0;
vis[0] = vis_token;
dist_arr[0] = 0;
int goal = -1;
while (head < tail) {
int cur = que[head++];
int c = cur >> K;
if (c == 399) { goal = cur; break; }
int mask = cur & (FULL - 1);
int nd = dist_arr[cur] + 1;
const bool* open = open_table[mask];
int an = adjN[c];
for (int a = 0; a < an; a++) {
if (!open[(int)adjDoor[c][a]]) continue;
int nx = cur + adjDelta[c][a];
if (vis[nx] != vis_token) {
vis[nx] = vis_token;
dist_arr[nx] = nd;
que[tail++] = nx;
}
}
int s = swFlat[c];
if (s >= 0) {
int nx = cur ^ (1 << s);
if (vis[nx] != vis_token) {
vis[nx] = vis_token;
dist_arr[nx] = nd;
que[tail++] = nx;
}
}
}
return goal >= 0 ? dist_arr[goal] : 0;
}
void reset_solution() {
current_doors.clear();
current_switches.clear();
memset(door_h, -1, sizeof(door_h));
memset(door_v, -1, sizeof(door_v));
memset(switch_map_, -1, sizeof(switch_map_));
memset(door_h_idx, -1, sizeof(door_h_idx));
memset(door_v_idx, -1, sizeof(door_v_idx));
memset(switch_idx_, -1, sizeof(switch_idx_));
memset(swFlat, -1, sizeof(swFlat));
buildAdj();
}
bool add_door(int d, int i, int j, int g) {
if ((int)current_doors.size() >= M) return false;
if (d == 0) {
if (door_h[i][j] != -1) return false;
door_h[i][j] = g;
door_h_idx[i][j] = (int)current_doors.size();
} else {
if (door_v[i][j] != -1) return false;
door_v[i][j] = g;
door_v_idx[i][j] = (int)current_doors.size();
}
setEdgeDoor(d, i, j, g);
current_doors.push_back({d, i, j, g});
return true;
}
void remove_door(int idx) {
Door x = current_doors[idx];
if (x.d == 0) { door_h[x.i][x.j] = -1; door_h_idx[x.i][x.j] = -1; }
else { door_v[x.i][x.j] = -1; door_v_idx[x.i][x.j] = -1; }
setEdgeDoor(x.d, x.i, x.j, -1);
if (idx + 1 != (int)current_doors.size()) {
current_doors[idx] = current_doors.back();
Door y = current_doors[idx];
if (y.d == 0) door_h_idx[y.i][y.j] = idx;
else door_v_idx[y.i][y.j] = idx;
}
current_doors.pop_back();
}
void set_door_g(int idx, int g) {
Door& x = current_doors[idx];
x.g = g;
if (x.d == 0) door_h[x.i][x.j] = g;
else door_v[x.i][x.j] = g;
setEdgeDoor(x.d, x.i, x.j, g);
}
bool add_switch(int i, int j, int s) {
if (switch_map_[i][j] != -1) return false;
switch_map_[i][j] = s;
swFlat[cellId(i, j)] = s;
switch_idx_[i][j] = (int)current_switches.size();
current_switches.push_back({i, j});
return true;
}
long long depthW[10], spineCoeff[10];
void precompute_coeff() {
memset(depthW, 0, sizeof(depthW));
memset(spineCoeff, 0, sizeof(spineCoeff));
int prev = -1;
for (int step = 1; step < FULL; step++) {
int nxt = __builtin_ctz((unsigned)step);
if (prev < 0) {
depthW[nxt]++;
spineCoeff[nxt]++;
} else if (prev != nxt) {
depthW[prev]++;
depthW[nxt]++;
if (prev < nxt) { spineCoeff[nxt]++; spineCoeff[prev]--; }
else { spineCoeff[prev]++; spineCoeff[nxt]--; }
}
prev = nxt;
}
depthW[prev]++;
spineCoeff[prev]--;
}
bool build_random_tree(FastRng& rng, int mode, array<vector<int>,400>& tree_adj) {
for (auto& v : tree_adj) v.clear();
if (mode == 0 || mode == 2) {
static int seen[400];
static int stamp = 0;
++stamp;
auto dfs = [&](auto& self, int u) -> void {
seen[u] = stamp;
int dirs[4] = {0, 1, 2, 3};
if (mode == 0) shuffle(dirs, dirs + 4, rng);
else {
// 少しだけゴールから遠回りするDFSを混ぜる
int bias[4];
for (int k = 0; k < 4; k++) {
int nr = rr[u] + di4[k], nc = cc[u] + dj4[k];
bias[k] = (nr < 0 || nr >= N || nc < 0 || nc >= N || cell_[nr][nc] == '#') ? -10000 : abs(19 - nr) + abs(19 - nc) + (int)(rng.next32() & 7);
dirs[k] = k;
}
sort(dirs, dirs + 4, [&](int a, int b){ return bias[a] > bias[b]; });
}
for (int idx = 0; idx < 4; idx++) {
int d = dirs[idx];
int nr = rr[u] + di4[d], nc = cc[u] + dj4[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N || cell_[nr][nc] == '#') continue;
int v = cellId(nr, nc);
if (seen[v] == stamp) continue;
tree_adj[u].push_back(v);
tree_adj[v].push_back(u);
self(self, v);
}
};
dfs(dfs, 0);
return true;
} else {
vector<pair<uint32_t, pair<int,int>>> edges;
edges.reserve(valid_h_doors.size() + valid_v_doors.size());
for (auto [i, j] : valid_h_doors) edges.push_back({rng.next32(), {cellId(i, j), cellId(i + 1, j)}});
for (auto [i, j] : valid_v_doors) edges.push_back({rng.next32(), {cellId(i, j), cellId(i, j + 1)}});
sort(edges.begin(), edges.end(), [](auto& a, auto& b){ return a.first < b.first; });
int dsu[400]; iota(dsu, dsu + 400, 0);
auto find = [&](auto& self, int x) -> int { return dsu[x] == x ? x : dsu[x] = self(self, dsu[x]); };
for (auto& e : edges) {
int a = e.second.first, b = e.second.second;
int ra = find(find, a), rb = find(find, b);
if (ra == rb) continue;
dsu[ra] = rb;
tree_adj[a].push_back(b);
tree_adj[b].push_back(a);
}
return true;
}
}
bool extract_path_and_branches(const array<vector<int>,400>& tree_adj, vector<int>& path, vector<Branch>& branches) {
int parent[400];
fill(parent, parent + 400, -2);
int q[400], head = 0, tail = 0;
q[tail++] = 0; parent[0] = -1;
while (head < tail) {
int u = q[head++];
if (u == 399) break;
for (int v : tree_adj[u]) if (parent[v] == -2) {
parent[v] = u;
q[tail++] = v;
}
}
if (parent[399] == -2) return false;
path.clear();
for (int u = 399; u != -1; u = parent[u]) path.push_back(u);
reverse(path.begin(), path.end());
int L = (int)path.size() - 1;
if (L < 10) return false;
bool on_path[400] = {};
for (int u : path) on_path[u] = true;
branches.clear();
for (int i = 0; i < L; i++) {
int u = path[i];
for (int v : tree_adj[u]) {
if (on_path[v]) continue;
int best_leaf = v, best_depth = 1;
auto dfs_branch = [&](auto& self, int x, int p, int dep) -> void {
if (dep > best_depth) { best_depth = dep; best_leaf = x; }
for (int y : tree_adj[x]) if (y != p && !on_path[y]) self(self, y, x, dep + 1);
};
dfs_branch(dfs_branch, v, u, 1);
branches.push_back({i, best_depth, best_leaf, v});
}
}
return (int)branches.size() >= 10;
}
bool select_branches_dp(const vector<int>& path, const vector<Branch>& branches, vector<Branch>& selected) {
int L = (int)path.size() - 1;
vector<int> br_idx[400];
for (int i = 0; i < (int)branches.size(); i++) br_idx[branches[i].spine_idx].push_back(i);
for (int m = 0; m < L; m++) {
sort(br_idx[m].begin(), br_idx[m].end(), [&](int a, int b){
if (branches[a].depth != branches[b].depth) return branches[a].depth > branches[b].depth;
return branches[a].leaf < branches[b].leaf;
});
}
static long long dp[11][405];
static int preM[11][405], preK[11][405], prePick[11][405];
const long long NEG = -(1LL << 60);
for (int k = 0; k <= 10; k++) for (int m = 0; m <= L; m++) {
dp[k][m] = NEG; preM[k][m] = preK[k][m] = prePick[k][m] = -1;
}
dp[0][0] = 0;
for (int m = 0; m <= L - 2; m++) {
for (int k = 0; k <= 10; k++) {
if (dp[k][m] <= NEG / 2) continue;
if (dp[k][m] > dp[k][m + 1]) {
dp[k][m + 1] = dp[k][m];
preK[k][m + 1] = k; preM[k][m + 1] = m; prePick[k][m + 1] = -1;
}
if (k < 10 && !br_idx[m].empty()) {
int b = br_idx[m][0];
long long val = dp[k][m] + depthW[k] * branches[b].depth + spineCoeff[k] * branches[b].spine_idx;
if (val > dp[k + 1][m + 1]) {
dp[k + 1][m + 1] = val;
preK[k + 1][m + 1] = k; preM[k + 1][m + 1] = m; prePick[k + 1][m + 1] = b;
}
}
// switch0とswitch1だけは同じ幹位置の2本枝を許す。序盤の高頻度bitが伸びるケースがある。
if (k == 0 && br_idx[m].size() >= 2) {
int b0 = br_idx[m][0], b1 = br_idx[m][1];
long long val = dp[k][m]
+ depthW[0] * branches[b0].depth + spineCoeff[0] * branches[b0].spine_idx
+ depthW[1] * branches[b1].depth + spineCoeff[1] * branches[b1].spine_idx;
if (val > dp[2][m + 1]) {
dp[2][m + 1] = val;
preK[2][m + 1] = k; preM[2][m + 1] = m; prePick[2][m + 1] = -2;
}
}
}
}
if (dp[10][L - 1] <= NEG / 2) return false;
selected.clear();
int k = 10, m = L - 1;
while (k > 0) {
int pk = preK[k][m], pm = preM[k][m], pp = prePick[k][m];
if (pk < 0) return false;
if (pp >= 0) selected.push_back(branches[pp]);
else if (pp == -2) {
selected.push_back(branches[br_idx[pm][1]]);
selected.push_back(branches[br_idx[pm][0]]);
}
k = pk; m = pm;
}
reverse(selected.begin(), selected.end());
return (int)selected.size() == 10;
}
long long candidate_score(const vector<int>& path, const vector<Branch>& sel) {
long long s = path.size();
for (int k = 0; k < 10; k++) s += depthW[k] * sel[k].depth + spineCoeff[k] * sel[k].spine_idx;
return s;
}
void push_top(vector<TreeCand>& tops, TreeCand&& cand, int keep = 6) {
tops.push_back(std::move(cand));
sort(tops.begin(), tops.end(), [](const TreeCand& a, const TreeCand& b){ return a.score > b.score; });
if ((int)tops.size() > keep) tops.pop_back();
}
int choose_extra_g(int pattern, int rank, int dist, FastRng& rng) {
if (pattern == 0) {
uint32_t r = rng.next32() % 100;
if (r < 62) return 19;
if (r < 74) return 17;
if (r < 84) return 15;
return rng.randint(20);
}
if (pattern == 1) return 19;
if (pattern == 2) {
if (rank % 5 == 0) return 17;
if (rank % 7 == 0) return 15;
return 19;
}
if (pattern == 3) {
if (rank < 8) return 19;
if (rank < 18) return 17;
if (rank < 28) return 15;
return (rank & 1) ? 19 : 13;
}
if (pattern == 4) {
// 距離が長いショートカットほど高bit奇数で閉じ、短い辺は状態依存をばらす。
if (dist >= 20) return 19;
if (dist >= 14) return 17;
if (dist >= 10) return 15;
static const int pool[8] = {19, 17, 15, 13, 11, 9, 7, 5};
return pool[(rank + dist) & 7];
}
return rng.randint(20);
}
void build_solution_from_tree(const TreeCand& cand, FastRng& rng, int pattern = 0) {
reset_solution();
const auto& path = cand.path;
const auto& br = cand.branches;
for (int k = 0; k < 10; k++) {
int leaf = br[k].leaf;
add_switch(rr[leaf], cc[leaf], k);
if (k >= 1) {
int u = path[br[k].spine_idx];
int v = br[k].root;
add_door(edgeDir(u, v), edgeI(u, v), edgeJ(u, v), 2 * (k - 1) + 1);
}
}
for (int k = 0; k <= 8; k++) {
int m = br[k + 1].spine_idx;
int u = path[m], v = path[m + 1];
add_door(edgeDir(u, v), edgeI(u, v), edgeJ(u, v), 2 * k);
}
int L = (int)path.size() - 1;
add_door(edgeDir(path[L - 1], path[L]), edgeI(path[L - 1], path[L]), edgeJ(path[L - 1], path[L]), 19);
int t_depth[400], t_parent[400];
auto dfs_t = [&](auto& self, int u, int p, int dep) -> void {
t_depth[u] = dep; t_parent[u] = p;
for (int v : cand.tree_adj[u]) if (v != p) self(self, v, u, dep + 1);
};
dfs_t(dfs_t, 0, -1, 0);
auto tree_dist = [&](int a, int b) {
int res = 0;
int x = a, y = b;
while (t_depth[x] > t_depth[y]) { x = t_parent[x]; res++; }
while (t_depth[y] > t_depth[x]) { y = t_parent[y]; res++; }
while (x != y) { x = t_parent[x]; y = t_parent[y]; res += 2; }
return res;
};
vector<pair<int, pair<int,int>>> back_edges;
for (auto [i, j] : valid_h_doors) {
int a = cellId(i, j), b = cellId(i + 1, j);
bool tree_edge = false;
for (int v : cand.tree_adj[a]) if (v == b) { tree_edge = true; break; }
if (!tree_edge) back_edges.push_back({tree_dist(a, b), {a, b}});
}
for (auto [i, j] : valid_v_doors) {
int a = cellId(i, j), b = cellId(i, j + 1);
bool tree_edge = false;
for (int v : cand.tree_adj[a]) if (v == b) { tree_edge = true; break; }
if (!tree_edge) back_edges.push_back({tree_dist(a, b), {a, b}});
}
sort(back_edges.rbegin(), back_edges.rend());
int rank = 0;
for (auto& be : back_edges) {
if ((int)current_doors.size() >= M) break;
int a = be.second.first, b = be.second.second;
int g = choose_extra_g(pattern, rank, be.first, rng);
add_door(edgeDir(a, b), edgeI(a, b), edgeJ(a, b), g);
rank++;
}
}
bool is_tree_edge(const array<vector<int>,400>& tree_adj, int a, int b) {
for (int v : tree_adj[a]) if (v == b) return true;
return false;
}
void save_solution(vector<Door>& bd, vector<SwOut>& bs) {
bd = current_doors;
bs.clear();
for (auto [i, j] : current_switches) bs.push_back({i, j, switch_map_[i][j]});
}
void load_solution(const vector<Door>& doors, const vector<SwOut>& sws) {
reset_solution();
for (auto s : sws) add_switch(s.i, s.j, s.s);
for (auto d : doors) add_door(d.d, d.i, d.j, d.g);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init_tables();
precompute_coeff();
int inN, inM, inK;
if (!(cin >> inN >> inM >> inK)) return 0;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> cell_[i][j];
for (int i = 0; i + 1 < N; i++) for (int j = 0; j < N; j++) if (cell_[i][j] == '.' && cell_[i + 1][j] == '.') valid_h_doors.push_back({i, j});
for (int i = 0; i < N; i++) for (int j = 0; j + 1 < N; j++) if (cell_[i][j] == '.' && cell_[i][j + 1] == '.') valid_v_doors.push_back({i, j});
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (cell_[i][j] == '.') valid_cells.push_back(cellId(i, j));
FastRng rng(0x9e3779b97f4a7c15ULL);
auto start = chrono::steady_clock::now();
const double TL = 1.94;
const double TREE_TIME = 1.08;
vector<TreeCand> tops;
int trials = 0;
while (true) {
if ((trials & 31) == 0) {
double e = chrono::duration<double>(chrono::steady_clock::now() - start).count();
if (e > TREE_TIME) break;
}
trials++;
array<vector<int>,400> tree_adj;
int mode = (rng.next32() % 100 < 55 ? 0 : (rng.next32() % 100 < 80 ? 1 : 2));
if (!build_random_tree(rng, mode, tree_adj)) continue;
vector<int> path;
vector<Branch> branches, selected;
if (!extract_path_and_branches(tree_adj, path, branches)) continue;
if (!select_branches_dp(path, branches, selected)) continue;
TreeCand cand;
cand.score = candidate_score(path, selected);
cand.path = std::move(path);
cand.branches = std::move(selected);
cand.tree_adj = std::move(tree_adj);
push_top(tops, std::move(cand), 14);
}
vector<Door> best_doors;
vector<SwOut> best_switches;
int bestT = -1;
int bestIdx = -1;
int bestPattern = 0;
if (tops.empty()) {
// 非常用。通常は通らない。
reset_solution();
int T = calcT();
bestT = T;
save_solution(best_doors, best_switches);
}
// v3: 上位候補木について、back edge扉型の複数パターンをexact Tで比較する。
// 木の理論値だけでは抜け道の閉じ方の差が見えないため、ここが一番効く。
for (int idx = 0; idx < (int)tops.size(); idx++) {
int maxPattern = (idx < 5 ? 5 : 3);
for (int pat = 0; pat < maxPattern; pat++) {
build_solution_from_tree(tops[idx], rng, pat);
int T = calcT();
if (T > bestT) {
bestT = T;
bestIdx = idx;
bestPattern = pat;
save_solution(best_doors, best_switches);
}
}
}
if (bestIdx >= 0) build_solution_from_tree(tops[bestIdx], rng, bestPattern);
else load_solution(best_doors, best_switches);
int currentT = calcT();
if (currentT < bestT) load_solution(best_doors, best_switches), currentT = bestT;
else save_solution(best_doors, best_switches), bestT = currentT;
const int PROTECTED = 19;
double temp0 = 6.0, temp1 = 0.02;
long long it = 0;
while (true) {
if ((it & 63) == 0) {
double e = chrono::duration<double>(chrono::steady_clock::now() - start).count();
if (e > TL) break;
}
++it;
double e = chrono::duration<double>(chrono::steady_clock::now() - start).count();
double t = min(1.0, max(0.0, (e - TREE_TIME) / max(0.001, TL - TREE_TIME)));
double temp = temp0 * pow(temp1 / temp0, t);
int op = rng.randint(100);
int nextT = 0;
if (op < 38 && (int)current_doors.size() < M && bestIdx >= 0) {
int d = rng.randint(2);
auto& vec = (d == 0 ? valid_h_doors : valid_v_doors);
if (vec.empty()) continue;
auto [i, j] = vec[rng.randint((int)vec.size())];
if ((d == 0 && door_h[i][j] != -1) || (d == 1 && door_v[i][j] != -1)) continue;
int a = cellId(i, j), b = (d == 0 ? cellId(i + 1, j) : cellId(i, j + 1));
if (is_tree_edge(tops[bestIdx].tree_adj, a, b)) continue;
int g;
uint32_t r = rng.next32() % 100;
if (r < 55) g = 19;
else if (r < 68) g = 17;
else if (r < 78) g = 15;
else g = rng.randint(20);
add_door(d, i, j, g);
nextT = calcT();
if (nextT > 0 && (nextT >= currentT || rng.real01() < exp((nextT - currentT) / temp))) currentT = nextT;
else remove_door((int)current_doors.size() - 1);
} else if (op < 58 && (int)current_doors.size() > PROTECTED) {
int idx = PROTECTED + rng.randint((int)current_doors.size() - PROTECTED);
Door old = current_doors[idx];
remove_door(idx);
nextT = calcT();
if (nextT > 0 && (nextT >= currentT || rng.real01() < exp((nextT - currentT) / temp))) currentT = nextT;
else add_door(old.d, old.i, old.j, old.g);
} else if (op < 80 && (int)current_doors.size() > PROTECTED) {
int idx = PROTECTED + rng.randint((int)current_doors.size() - PROTECTED);
int oldg = current_doors[idx].g;
int ng;
uint32_t r = rng.next32() % 100;
if (r < 42) ng = 19;
else if (r < 55) ng = 17;
else if (r < 65) ng = 15;
else ng = rng.randint(20);
if (ng == oldg) continue;
set_door_g(idx, ng);
nextT = calcT();
if (nextT > 0 && (nextT >= currentT || rng.real01() < exp((nextT - currentT) / temp))) currentT = nextT;
else set_door_g(idx, oldg);
} else if ((int)current_doors.size() > PROTECTED && bestIdx >= 0) {
// 余剰扉を別の非木辺へ移動。googleasの高速評価器を活かした軽量近傍。
int idx = PROTECTED + rng.randint((int)current_doors.size() - PROTECTED);
Door old = current_doors[idx];
int d = rng.randint(2);
auto& vec = (d == 0 ? valid_h_doors : valid_v_doors);
if (vec.empty()) continue;
auto [ni, nj] = vec[rng.randint((int)vec.size())];
if ((d == 0 && door_h[ni][nj] != -1) || (d == 1 && door_v[ni][nj] != -1)) continue;
int a = cellId(ni, nj), b = (d == 0 ? cellId(ni + 1, nj) : cellId(ni, nj + 1));
if (is_tree_edge(tops[bestIdx].tree_adj, a, b)) continue;
remove_door(idx);
add_door(d, ni, nj, old.g);
nextT = calcT();
if (nextT > 0 && (nextT >= currentT || rng.real01() < exp((nextT - currentT) / temp))) currentT = nextT;
else {
remove_door((int)current_doors.size() - 1);
add_door(old.d, old.i, old.j, old.g);
}
}
if (currentT > bestT) {
bestT = currentT;
save_solution(best_doors, best_switches);
}
}
cout << best_doors.size() << '\n';
for (const Door& d : best_doors) cout << d.d << ' ' << d.i << ' ' << d.j << ' ' << d.g << '\n';
cout << best_switches.size() << '\n';
for (const SwOut& s : best_switches) cout << s.i << ' ' << s.j << ' ' << s.s << '\n';
return 0;
}
この解説はChatGPTを使用しており、必ずしも正しいとは限りません。重要な情報は確認するようにしてください。
投稿日時:
最終更新: