Topcoder Marathon Match 166「HexTiles」に参加した。最終結果は 92.460 点 / 75 人中 34 位（暫定は 91.353 点・33 位）。

この記事は、前半が本番の解法、後半が会期終了後の延長戦の話になる。

前半で積んだのは、差分評価・焼きなまし・狙い撃ち再接続といった、スコアを登るための自然な戦略だ。対して後半で実装したのはたった 1 手だが、経路を伸ばすほどスコアが上がる問題で、あえて経路を短く繋ぎ直すという逆転の発想を持っていて、とても面白かった。順位表換算で +2.12%（約 7.6 順位ぶん）にあたる。

取り組み方

このコンテストは Claude Code と組んで取り組んだ。方針を決め、何を測るかを選び、採否を判断したのは私で、実装・計測・結果の整理は Claude Code に任せた。次の一手の提案も Claude Code から上がってくるが、採るかどうかは私が決めている。

この記事も Claude Code が作業ログとソースコードから起草し、私が監修した。数字はすべて測定記録から引いている。

作業の土台にしているのは自作のテンプレート WaTeR-7/ahc-template（CC0）で、new.sh を叩くとコンテストごとの独立リポジトリが生える。掃引・paired 統計・byte 一致照合のスクリプト一式と、AI エージェント向けの作業規約（CLAUDE.md / AGENTS.md）、過去回の知見置き場が入っている。この記事で出てくる測定の作法は、だいたいそこに書いてあるものだ。

問題

六角形のグリッドがある。1 辺 N 枚（N は 3 から 20）で、タイルの総数は $T = 3N^2 - 3N + 1$。N=20 なら 1141 枚。

各タイルは 3 本の弦を持つ。弦はタイルの 6 辺のうち 2 辺を結ぶ通路で、3 本で 6 辺すべてを使い切る。タイルを 60° 回すと弦の配置も一緒に回る。向きは rot が 0 から 5 の 6 通り。

隣り合うタイルの弦がつながって経路になり、盤面の境界辺（exit）で外に出る。exit は $6(2N-1)$ 個あって、目標ペア（exit 同士の完全マッチング、$P = 3(2N-1)$ 本）が入力で与えられる。タイルを回して、経路の両端が目標ペアどおりになるようにする。

実際に N=3（最小サイズ）を解かせた盤面を示す。ラベルは exit の番号と、その相手のペアを表す。灰色が目標ペアどおりに繋がっていない経路、色付きが繋がった経路で、水色のタイルがボーナスタイル。

タイル 1 枚を見ると、6 辺のうち 2 辺ずつを結ぶ弦が 3 本ある。60° 回すと張り方が変わる。

スコアは次の式で決まる。

$$\text{score} = \text{numMatches} \times \left( \sum_{p \in \text{matched}} \text{len}(p)\,(b_p + 1) \;-\; m M \right)$$

• numMatches … 目標どおりにつながった経路の本数
• len(p) … 経路 p が通ったタイル数（同じタイルを 2 回通れば 2）
• b_p … 経路が通った相異なるボーナスタイルの数。ボーナスタイルは B 個（1 から 10）
• m … 出力した回転操作の数、M … 1 手あたりのペナルティ（1 から 5）

負なら 0。制限時間 10 秒、提出は単一の .rs。評価は相対評価で、各ケース「自分 / 全参加者の最大」の和を 100 に正規化する。

本番の解法

0. 操作列ではなく配置問題

問題文は「回転操作の列を出力せよ」と言っている。だが採点器を読むと、スコアは最終盤面と手数 m だけの関数で、操作の順序にはまったく依存しない。

しかも手数は配置から一意に決まる。タイル t の目標向きを $G_t$、初期向きを $s_t$ とすると

$$m(G) = \sum_t \min(\delta_t,\, 6 - \delta_t), \qquad \delta_t = (G_t - s_t) \bmod 6$$

が最小手数で、これ以外に払いようがない。

つまり**探索するのは操作列ではなく「各タイルの最終的な向き」**で、$6^T$ 通りの割り当て問題になる。ここが決まれば、あとは局所探索の話になる。

1. 差分評価

焼きなましの試行回数は 1 手あたりの評価コストで決まる。ここを次のように変えた。

	計算量	いつ払うか
全数評価（最初の版）	$O(3T)$	候補を出すたび
差分評価	$O(B) \approx O(1)$	候補を出すたび
差分更新	$O(L)$	採用されたときだけ

$T$ はタイル数、$B$ はボーナスタイルの数（高々 10）、$L$ は繋ぎ変わった経路の長さ。 N=20 なら $3T = 3423$ なので、候補 1 つの値段が 3 桁ぶん下がる。

持っている情報は 2 種類ある。弦ごと（弦は c = 3t + k で一意に振る）に

• pid[c] … その弦が属する経路の番号
• pos[c] … その経路の何番目か
• dir[c] … 経路をどちら向きに通るか

経路ごとに

• pa[p], pb[p] … 両端の exit（閉路なら無し）
• plen[p] … 長さ
• pmask[p] … 通ったボーナスタイルのビットマスク

b_p は「相異なるボーナスタイルの数」なので、単なるカウンタでは合流・分裂のときに重複が数えられない。ここは B が高々 10 であることを使って集合そのものを 16 bit で持つ。合流は OR、b_p は popcount で、どちらも $O(1)$ になる。

評価は 2 段。まずタイル t の弦 3 本を外すと、t を通っていた高々 3 本の経路が切れて、高々 6 片の断片になる（t に入る 6 スロットが、それぞれちょうど 1 つの断片の端になる）。各断片の長さは pos の引き算で出る。問題はボーナスマスクで、「経路 p の pos が lo..hi の範囲に入るボーナス弦」を集める必要があるが、ボーナス弦は全部で高々 3B = 30 本しかないので、その 30 本を舐めて pid と pos を見れば済む。盤面の大きさにも経路長にも依存しない。

次に、新しい向きが決める 3 本の弦で 6 スロットを繋ぎ直し、断片を数珠つなぎに辿って長さを足しマスクを OR する。断片は高々 6 片なので、ここも定数。

$$\Delta\text{matches},\ \Delta\text{total} \;=\; O(B) \;=\; O(1)$$

重要なのは、この評価が読み取りしかしないことだ。pid も pos も書き換えないので、棄却された手の巻き戻しコストがゼロになる。実際に採用されたときだけ、繋ぎ変わった経路に沿って pid/pos/dir を振り直す $O(L)$ を払う。

さらに後の版では、同じタイルの 6 通りの向きが同じ「外す」処理を共有できることを使って、6 候補を 1 回の切り出しで評価するようにした。

2. 焼きなましの目的関数を対数にする

登る関数を、真のスコアではなく

let f = matches as f64 * (total - moves * penalty) as f64;
f.signum() * (1.0 + f.abs()).ln()      // ← これを登る

にした。

焼きなましは、悪化する手も確率的に受け入れることで局所解から抜ける。受け入れるかどうかは、悪化幅 $\Delta$ と温度 $T$ から $\exp(\Delta/T)$ の確率で決める（Metropolis 基準）。

注意すべきなのは、上の変換は単調なので「どちらの盤面が良いか」の順序を 1 つも変えないことだ。平坦な領域が平坦でなくなるわけでもない。変わるのは Metropolis 基準が見る差分 $\Delta$ のほうで、

$$\Delta g \;=\; \ln\frac{f_{\text{new}}}{f_{\text{cur}}} \;\approx\; \frac{\Delta f}{|f|}$$

つまり絶対差が相対変化に化ける。効くのは 2 点。

① 温度がスケール不変になる。 スコアは走行の最初と最後で桁が変わり、seed 間でも桁が違う。生スコアだと、同じ温度が序盤ではほぼ全部を受理し終盤ではほぼ全部を棄却する。対数なら「1% の改悪」がどこでも同じ確率になる。

② 積であることの害が消える。 目的関数は matches × X という積だ。生スコアだと一致を 1 本失う損は $X$ そのもので、一致が 15 本でも 117 本でも同じ絶対値になる。対数なら $\ln\frac{m}{m-1} \approx 1/m$ で、持っている本数に対する相対的な損として値付けされる。

②は測定でそのまま見える。効果は N に強く偏り、小さい盤面ほど大きく、N が 16 以上ではほとんど消える。小さい盤面ほど一致の上限本数が少なく（N=3 なら 15 本）、1 本の重みが相対的に大きい ── 積の害がいちばん強く出るところで、いちばん効いている。

3. 候補を待つのではなく作る

素の焼きなましは「ランダムなタイルをランダムな向きに回す」。これだと目標ペアがつながる回転を引くのは偶然頼みになる。

そこで、まだ一致していない exit ペアを選び、その 2 本の目標経路が交差するタイルを逆算して、そこを狙って回す手を入れた。大きい盤面ほどよく効いた。

さらに「交差するタイルが無い」ときのために、隣接する 2 タイルを同時に回す橋渡しと、k タイルぶんの配線路を Dijkstra で引くルータを足した。候補を待つのではなく作りにいく方向。

4. 壊してから、同じ手の中で直す

狙い撃ちには落とし穴がある。狙ったペアは 94〜99% の確率で作れているのに、numMatches が実際に増えるのは 7〜32% しかなかった。同じ回転が、平均 1 本の既存の一致を巻き添えで壊している。

対策は「壊さない候補を選ぶ」ではなく（候補はそもそも普段 1 本しかない）、壊れた側を同じ手の中で張り直すことだった。2 タイルを回した最終状態だけを Metropolis に掛ける。1 手ずつ判定すると 1 手目が必ず一致を壊すので絶対に通らない。

この形は結局 4 回効いた。通った機構は 4 本とも「壊してから同じ手の中で直す」原子複合手になっている。図2 の補題（一致を保ったまま動かせるのは ±60° だけ）から考えれば当然で、何かを変えるには必ず一度壊すしかない。

5. N でゲームが変わる

途中で N を 4 つのクラスに割って、別々に最適化するようにした。

クラス	N	件数比	手数 / total	挙動
1	3–6	22%	24.8%	手数ペナルティが支配する別ゲーム。多スタートで 8 回引き直す
2	7–10	28%	13.3%	同上（多スタート）
3	11–15	22%	8.6%	1 本を深く
4	16–20	28%	8.2%	1 本を深く

境界は測って決めた。7 は手数比が半減する点、16 は橋渡しの作用域が切れる点。

これを入れてから、掃引の seed にほかのクラスを混ぜてはいけないことが分かった。作用域の外の seed は平均 0・分散だけを持ち込むので、t 値が「1 / 作用域の割合」だけ目減りする。N >= 16 のレバーだと 3.6 倍の損。クラス別の seed に分けただけで、同じ計算時間のまま検出力が 2〜3.6 倍になった。

結果

提出	版	スコア	順位
#9	クラス別に構造を変える	90.253	21/54
#12	クラス4 の近傍幅 4→3	90.961	31/69
#13	クラス4 の狙い撃ち試行数 8→16	91.206	28/73
#14	クラス4 の引き戻し閾値	91.463	32/73
#17（最終提出）	ルータ ＋ 巻き添え修復	91.353	33/75

順位が上下しているのは他人が伸びているから。**順位密度は「1% ≒ 3.6 順位」**で、終盤は伸ばさないと落ちる。実際 #13 → #14 はスコア +0.28% でも順位は 4 つ下がった。

表のスコアはどれも暫定順位表（100 ケース）の値。最終順位表（5000 ケース）では 92.460 点 / 34 位、首位は 99.790 点だった。

延長戦

最終日に「近いペアは短く成立し、遠いペアはたくさんのタイルを必要とする」というペアの性質を使っていないことを指摘したが、実装まで辿り着けずに会期が終わった。提出はできないが、延長戦として 1 日だけ取り組んだ。

1. ボーナスタイルが赤字

盤面には保存則がある。全タイルが弦を 3 本持ち、どの弦も必ずどれかの経路に属するので

$$\sum_p \text{len}(p) = 3T \quad \text{（盤面の向きをどう変えても定数）}$$

が成り立つ。一致経路が占める割合は実測で 0.97 から 1.00 なので、$\sum_{\text{matched}} \text{len}$ もほぼ定数になる。長さの総量は動かせず、動かせるのは配分だけということになる。

total は $\sum \text{len}(b+1)$ なので、同じ 1 セグメントでも、ボーナスを全部載せた長い経路（以下トランク）の下にあれば約 10 倍の価値になる。長さは集中しているほど良い。

ここまでに入れた機構 ── 狙い撃ち再接続・橋渡し・ルータ・巻き添え修復 ── は、マッチ率を上げることと、マッチした経路の len を伸ばすことには有効だった。しかしボーナスタイルを狙ってスコアを取ることはできていなかった。倍率 $b+1$ は経路がどのボーナスタイルを通るかで決まるのに、その倍率を意識して長さを配る手が 1 つも無い。

実際、トランクは盤面の $3T$ のうち 53〜80% しか占めておらず、残りは倍率 1 の短い経路に散っていた。一致本数と集中度は同じ $3T$ を奪い合うので、探索は一致の側へ一方向に流れる。

2. ペアの距離と waste

2 つの exit の間の六角距離は、その経路が最低限通らなければならないタイル数を決める。

$$\begin{aligned} L_{\min}(p) \;&=\; \text{hexdist}(\text{exit}_a,\ \text{exit}_z) + 1 \\[2pt] \text{waste}_p \;&=\; \max\bigl(0,\ \text{len}_p - L_{\min}(p)\bigr) \end{aligned}$$

$L_{\min}$ を下回ると一致が壊れるが、それより上の長さは一致を保つのに要らない。距離は「どこまで削ってよいかの床」を与える量だった。裏返すと、経路を短くしても失うものが無い区間が存在する。実測では、非トランク一致経路の長さの 37〜57% がこの床の上にあった。

total は経路が長いほど大きくなるので、ここまでの機構はすべて経路を伸ばす方向に働いてきた。waste を削る手はその逆で、あえて短く繋ぎ直す。総量が保存されている以上、削った長さは消えずに他の経路へ回るので、倍率の高いトランクの下に移せば同じ長さがそのまま高く売れる。

3. 実装した張り直し

足した手はひとつ。waste の大きい一致経路を選び、Dijkstra で測地線に張り直す。削れたぶんは保存則により他の経路へ回り、その配り直しは焼きなましがやる。

$$\text{gain} = \text{waste}_Q \times \big( (b_{\text{trunk}}+1) - (b_Q+1) \big)$$

b を増やす手ではない（長い経路の b/B はすでに 93.8〜100% で飽和している）。動かすのは倍率が掛かる「量」のほう。

4. 結果

同じ seed を、張り直し無しと有りで解かせた盤面を並べる（反復数を揃えてある）。

集合	Δlog ± se	勝/負	件数比	順位表換算
クラス1 (N3-6)	+0.130% ± 0.126	75/50	22%	null
クラス2 (N7-10)	+1.903% ± 0.165	168/32	28%	+0.53%
クラス3 (N11-15)	+2.889% ± 0.165	181/18	22%	+0.64%
クラス4 dev	+3.289% ± 0.185	184/16	—	—
クラス4 holdout	+3.299% ± 0.188	189/11	28%	+0.92%
			合計	+2.12%

クラス4 は dev と holdout が 0.01% 差で一致した。クラス1 で効かないのは、N が 3 から 6 だと $3T$ が 57 から 273 しかなく、経路が短くて waste が生まれないため。

順位表換算 +2.12%、順位密度でいえば約 7.6 順位にあたる。首位との差 7.3% のうち 29% を 1 本で埋めたことになる。

学び ── 問題の構造を探索に組み込む

汎用の焼きなましやビームサーチは、それだけなら誰でも書ける。上位と差がつくのも、より良い解に届くのも、問題固有の構造を探索そのものに組み込めたかどうかだ。汎用側を強くする作業のほうには、手を入れれば伸びるという保証がない。頭では分かっているのに毎回ここで足踏みする。今回もそうだった。

使った性質	どこで
スコアは最終盤面と手数だけの関数で、操作の順序に依らない	0 節
最小手数が閉じた式 $m(G) = \sum_t \min(\delta_t,\, 6-\delta_t)$ で決まる	0 節
$b_p$ は相異なるボーナスタイルの数で、$B \leq 10$ なので集合を 16 bit で持てる	1 節
ボーナス弦は盤面全体で高々 $3B = 30$ 本しかない	1 節
異なる 2 つの向きが共有する弦は高々 1 本（一致を保てるのは ±60° だけ）	4 節
一致経路が 2 本以上通っているタイルには、一致を壊さない回転が存在しない	4 節
$\sum_p \text{len}(p) = 3T$ が盤面の向きに依らず定数	延長戦 1 節
$L_{\min}$ が 2 つの exit のタイル間の六角距離 + 1 で決まる	延長戦 2 節

表のとおり、問題固有の性質を取り込めた部分はある。75 人中 34 位と、上位半分に入れたのはそのおかげだ。問題は内訳のほうだった。

0 節の 2 つは、そもそものベース選択を決めている。スコアが操作の順序に依らないなら、1 手ずつ決めていく逐次決定ではない ── ビームサーチで刻む「段」がそもそも存在しないので、向き空間の局所探索しか残らない。焼きなましを選んだのは好みではなく、問題の性質がそう決めた。

残りはこうなる。スコアは $\text{numMatches} \times (\sum \text{len}(b+1) - mM)$ という積で、因子が 2 つある。1 節の 2 つは差分評価を $O(1)$ にするもの、4 節の 2 つは numMatches を取りに行くためのものだ。一致を保てる回転が存在しないという性質から、壊してから同じ手の中で直すという原子複合手の形が決まっている。

つまり問題固有の性質はちゃんと使っていて、ただし積の片方しか最適化していなかった。もう片方 ── 長さと倍率の配り方 ── を動かす性質に、手が伸びていない。それが表の下 2 つだ。しかも保存則は「全タイルが弦を 3 本持ち、どの弦も必ずどれかの経路に属する」から、$L_{\min}$ は六角距離という純粋な幾何から出る。実験は 1 つも要らない。初日に紙の上で導けたもので、8 日かけて見つけたものではない。

そして 5 本のレバーが連続して効かなくなったとき、「探索が近最適に収束した」と読んで、さらに強い手を作る方向に答えていた。実際には買える軸がひとつ足りなかっただけで、強さの問題ではなく構造の問題だった。

汎用側を伸ばす作業は、手数が無限にあって、しかも一つ一つがそれらしく見えるので、いくらでも時間を吸う。構造を読み直す作業はそう見えない。だから毎回こちらが後回しになる。

次に同じことをしないために言語化しておく。

• スコア式の各項が何を測っているかを、実装の前に紙の上で分解する。 今回なら $\sum \text{len}(b+1)$ が「量 × 倍率」の形で、しかも量が保存されていることは初日に書けた。
• レバーが連続して負に出たら、探索の強さではなく「買えていない軸」を疑う。 収束の証拠ではない。