A - Layered Barcode Display Editorial by matsu7874

With AI部門 暫定22位

AHC074 振り返り：人間と AI エージェントで作った解答の解説

はじめに

AHC074 の我々の解答を解説する。 最終提出は 1 ケースあたり 10,674.1（1 注文あたり約 10.4 手、誤り 0）で、コンテスト終了時点の With AI 部門の順位表では 22 位だった（最終提出の直後は 20 位）。 判定の点の最良は、一つ前の提出の 10,667.7 である。 コードは Claude Code が書き、人間は方針の指示と提出を担当した。

以下では、解法の大方針、点数の推移と点に効いた工夫、人間の貢献、AI の貢献を順に書く。 数字は作業の記録（実験ログ、コミット、セッションの記録）から引いた。

解法の大方針

解法は、最初に紙の模様を決める 設計フェーズ と、注文ごとに手を決める 注文フェーズ に分かれる。 制限時間 2 秒のうち、1.85 秒までを使う。

フェーズ 時間 中身
設計フェーズ 起動から 1.175 秒まで（速い環境では最大 1.275 秒まで） 順序の紙の割り当て表と、型紙の組と層を決める
注文フェーズ 設計の終わりから 1.85 秒まで（約 0.675 秒） 1,024 件の注文の手を決める（1 件あたり平均約 0.66 ms）

設計フェーズの終わりは、環境の速さの目安から決める。 割り当て表の最初の候補を作り終えた時刻を u 秒とし、設計の終わりを 1.7 − 15u 秒程度にする（1.175 秒から 1.275 秒の範囲に収める）。 判定環境に近いと見ている速さの模擬では下限が効き、設計フェーズは 1.175 秒で終わる。 増やした時間を設計フェーズと注文フェーズのどちらに配るかは、両方の値打ちを測って決めた（時間の上限を延ばした時の増分は、半分ずつ配った）。

全体の構造

窓は、商品の色を見せる 内容窓（38 個）と、紙を取り出すための 制御窓（26 個）に分けた。 紙の重なりは、上から ① 今の注文の型紙、② 順序の紙 6 枚、③ 型紙の層の束、の 3 つの部分からなる。 次の図は、内容窓のうち 8 個と制御窓のうち 4 個だけを描いたものである。

     w1 w2 w3 w4 w5 w6 w7 w8 …  c0 c1 c2 c3 …
X     ?  ?  ?  ?  ?  ?  ?  ?     ?  #  .  .     ① 今の注文の型紙（共有の型紙、層 1）
P1    B  .  .  W  .  .  B  .     .  .  .  .     ② 順序の紙
P2    W  B  .  .  .  .  .  .     .  .  .  .
P3    .  W  B  .  .  .  .  W     .  .  .  .
P4    .  .  W  B  B  .  .  .     .  .  .  .
P5    .  .  .  .  W  B  .  B     .  .  .  .
P6    .  .  .  .  .  W  W  .     .  .  .  .
T0    #  #  #  #  #  #  #  #     #  .  .  .     ③ 層 0 の単独の型紙
S0    ?  ?  ?  ?  ?  ?  ?  ?     #  .  .  .        層 0 の共有の型紙
T1    #  #  #  #  #  #  #  #     #  #  .  .        層 1 の単独の型紙
S1    ?  ?  ?  ?  ?  ?  ?  ?     ?  #  .  .        層 1 の共有の型紙
T2    #  #  #  #  #  #  #  #     #  #  #  .        層 2 の単独の型紙
S2    ?  ?  ?  ?  ?  ?  ?  ?     ?  ?  #  .        層 2 の共有の型紙
…                                                  （下の層ほど、不透明な制御窓が 1 つずつ増える）

w1〜w8 は内容窓、c0〜c3 は制御窓である。 記号の意味は次のとおり。

  • B は黒、W は白、. は透明。
  • # は黒か白のどちらか（透明にはならない）。
  • ? は黒、白、透明のどれもあり得る。

各部分の中身は次のとおりである。

  • ③ は 型紙（商品のバーコードを写した紙）の束で、型紙は制御窓のどこまでが不透明かで 層 に分かれる。 各層には単独の型紙と共有の型紙が何枚かずつあり、図では 1 枚ずつ描いた。
    • 単独の型紙（T）は、内容窓がすべて黒か白で、穴がない。
    • 共有の型紙（S）は、2 商品で色が違う内容窓が穴（透明）になる。 制御窓では、自分の層の取っ手の窓（層 1 なら c1）は 2 商品の色をそろえて必ず不透明にし、それより浅い制御窓には穴があり得る。
  • ② の 順序の紙 は層とは別の 6 枚で、③ より上に置く。 内容窓ごとに、6 枚のうちちょうど 2 枚が黒と白で、残りの 4 枚は透明になる（例えば w1 は P1 が黒、P2 が白）。 制御窓では全部透明なので、③ の型紙の取り出しを邪魔しない。
  • ① は、注文が来た時に ③ から掘り出して一番上に置いた型紙である。

ほかに、② の上に、1 窓だけが不透明な動かさない紙が 1 枚あるが、図では省いた。

型紙と階段

型紙を一番上に置けば、表示がその商品になる。 ただし紙が商品より少ないので、全商品に 1 枚ずつは作れない。 そこで、色の多くが一致する 2 商品で 1 枚の型紙を共有し、2 商品で色が違う窓は透明（穴）にした。 最終版は共有の型紙が 71 枚、単独の型紙が 114 枚である。

層 a の型紙は、制御窓 c0〜ca で不透明にする。 同じ層の型紙を束にし、浅い層（不透明な制御窓が少ない層）から順に上に重ねる。 図の ③ のとおり、全体は 階段 の形になる。

この形にすると、どの層の型紙も取り出せる。 例えば制御窓 c2 では、それより上の層 0 と層 1 の型紙が透明なので、層 2 の束の一番上の型紙が見えていて、そのまま動かせる。 制御窓 c2 が、層 2 の型紙の 取っ手 になっている。 束の 2 枚目以降は、上の型紙をどかしてから取り出す（掘り出し）。 規則から導いた性質の一つに「露出する窓の数と、目的の型紙を掘り出す手数は釣り合う」というものがあり、階段はこの釣り合いの境界に乗る。

その代わり、図の ① のように浅い層の型紙を一番上に出すと、その型紙が透明な制御窓（c2、c3、…）には下の層の型紙の色が出る。 それが商品の色と違えば、紙を動かして合わせ直す（修正）。 11 月 2 日の時点では、1 注文あたり約 12.2 手のうち 5.8 手が修正だった。

共有の型紙の穴の埋め方：補充の紙から順序の紙へ

共有の型紙には、2 商品で色が違う内容窓に穴が開いている。 穴には下の紙の色が出るので、注文の商品の色が穴に出るように、型紙の下に何かを置かなければならない。 この「何か」の作り方を、11 月 5 日に大きく変えた。

小さな例で比べる。 共有の型紙 S が商品 x と y を担当し、内容窓 w1〜w4 が S の穴だとする。 ほかの窓では x と y の色が同じなので、S はそこをその色で覆っている。 穴の窓では、x と y の色はちょうど逆になる。

          w1 w2 w3 w4
商品 x     B  W  B  B
商品 y     W  B  W  W
型紙 S     .  .  .  .

B は黒、W は白、. は透明を表す（以下の図も同じ）。

補充の紙：模様ごとに 1 枚用意する

当初は、穴の窓で商品の色と完全に一致する 補充の紙 で穴を埋めていた。 この例では、x 用の Fx と y 用の Fy の 2 枚が要る。 x の注文では Fx を、y の注文では Fy を S の直下に置く。

x を出す時（上から）          y を出す時（上から）
          w1 w2 w3 w4                   w1 w2 w3 w4
S          .  .  .  .         S          .  .  .  .
Fx         B  W  B  B         Fy         W  B  W  W
表示       B  W  B  B         表示       W  B  W  W

1 枚の補充の紙は、穴の窓の色がその紙と完全に一致する商品しか担当できない。 そのため、すべての共有の型紙の穴を賄うのに 28 枚を使っていた。 詰め方を工夫しても、24〜26 枚が下限だった。

順序の紙：数枚の紙の並べ方で模様を作る

順序の紙は、不透明な窓が少ない紙を数枚重ね、その上下の順で色を作る。 設計で、内容窓ごとに次の 2 つを決めておく。

  • どの 2 枚の順序の紙に任せるか
  • その 2 枚のどちらを黒にするか（もう一方は白）

その窓ではその 2 枚だけを不透明にするので、窓には 2 枚のうち上にある方の色が出る。 内容窓 1 つにつき不透明な順序の紙は 2 枚だけなので、最終版（6 枚、内容窓 38 個）では、1 枚の順序の紙が黒か白になる窓は平均で約 13 個しかなく、残りは透明である。 例では順序の紙を A、B、C の 3 枚とし、次の割り当て表を使う。

窓 任せる 2 枚 黒の紙
w1 A と B A
w2 A と B B
w3 B と C B
w4 A と C A

紙ごとに見ると、模様は次のようになる。

          w1 w2 w3 w4
A          B  W  .  B
B          W  B  B  .
C          .  .  W  W

この割り当て表は、設計の時に一度決めたら注文の間は変わらない。 設計の目標は、共有の型紙にしたい商品の組を、できるだけ多く「表せる」ようにすることである。 組を表せるとは、組の 2 商品のどちらを出す時も、順序の紙の並べ方で穴の色を出せることをいう。

組を表せるかの判定

組の片方の商品について、穴の窓ごとに「どちらの紙が上なら、その商品の色が出るか」を割り当て表から読む。 窓ごとに、上にすべき紙から下にすべき紙への矢印が 1 本決まる。

組 x と y では、x（B W B B）から次の矢印が決まる。

窓 x の色 必要な向き
w1 黒 A が上（A → B）
w2 白 黒の紙 B より A が上（A → B）
w3 黒 B → C
w4 黒 A → C

矢印は A → B、B → C、A → C の 3 本で、同じ 2 枚（A と B）を任された w1 と w2 は同じ向きを求めている。 矢印をたどって元に戻る道（閉路）もない。 だから A、B、C の順に並べれば、x の色がすべて出る。 y は穴の色がすべて逆なので矢印もすべて逆になり、C、B、A の順で出せる。

x を出す時（上から）          y を出す時（上から）
          w1 w2 w3 w4                   w1 w2 w3 w4
S          .  .  .  .         S          .  .  .  .
A          B  W  .  B         C          .  .  W  W
B          W  B  B  .         B          W  B  B  .
C          .  .  W  W         A          B  W  .  B
表示       B  W  B  B         表示       W  B  W  W

表せない組の例も二つ挙げる。

  • 穴が w1 と w2 で、商品が「黒 黒」を求める組は表せない。 w1 の黒には A → B が、w2 の黒には B → A が要り、同じ 2 枚に逆の向きを求めるからである。
  • 穴が w2、w3、w4 で、商品が「白 黒 白」を求める組も表せない。 w2 から A → B、w3 から B → C、w4 から C → A が要り、A → B → C → A と一周する閉路になるので、どう並べても満たせない。

順序の紙を頂点、窓を任せる 2 枚の組を頂点の間の線と見ると、この判定はグラフの言葉で書ける。 そのため、窓を任せる 2 枚の組を 辺 と呼んでいる。 順序の紙が 6 枚なら、辺は全部で 15 本ある。

  • 穴の窓ごとに出したい色が決まっているので、その窓の辺では 2 枚の上下が決まり、辺は向きのついた有向辺になる。 穴でない窓は型紙が覆うので、その窓の辺の上下は自由である。
  • 有向辺をすべて満たす並び方は、そのグラフのトポロジカルソートで得られる。
  • 同じ辺に逆向きの要求があるか、有向辺に閉路があると、トポロジカルソートはできない。 前に挙げた二つの表せない例が、それぞれに当たる。
  • トポロジカルソートの結果は普通は複数ある。 注文の時は、その中から今の並びから最少の手数で移れるものを選ぶ（後の「注文の時の計算」）。

割り当て表の作り方

割り当て表を変えると、表せる組が入れ替わる。 例えば上の表で w2 の黒の紙を B から A に替えると、「黒 黒」を求める組は表せるようになる（w1 も w2 も A → B を求める）。 代わりに組 x と y は表せなくなる（w1 は A → B、w2 は B → A を求める）。

実際の設計では、次の形でこれを最適化する。

  • 候補の組は、256 商品のすべての組のうち、色が違う窓が 24 個以下の組である。
  • 候補の組ごとに重みを付ける。 色が違う窓が少ないほど重く、矢印で上下が決まる紙の組が少ないほど重くする（上下が決まる組が少ないほど、注文の時の並べ替えの手数が少ない）。
  • 目的は、表せる組の重みの和である。 正確には、商品ごとに表せる組の重みを足し、その 0.85 乗を全商品で足す（一部の商品に組が偏らないようにするため）。
  • 窓を 1 つ選び、その窓の割り当ての選択肢すべて（6 枚なら辺 15 本 × 黒の紙 2 通りで 30 通り）について目的の値を計算し、良い選択肢ほど高い確率で選び直す（焼きなまし法の一種の熱浴法）。 これを数万回繰り返す。

その後の型紙の設計（どの商品を組にし、どの層に置くか）では、ここで表せるとされた組の中からだけ、共有の型紙の組を選ぶ。

注文の時の計算

共有の型紙の商品の注文が来たら、判定で作った矢印をすべて満たす並び方に、今の並びから最少の手数で移す。

例えば、x を出した後（上から S、A、B、C）に y の注文が来たとする。 行き先は C、B、A である。 C はどの窓でも見えていない（w1、w2、w4 では A が、w3 では B が C より上にある）ので、直接は動かせない。 そこで、まず見えている A を C の下へ移す（S、B、C、A）。 すると w4 で C が見えるようになるので、次に C を S の直下へ移す（S、C、B、A）。 合わせて 2 手である。

順序の紙が 6 枚なら、並び方は 720 通りしかない。 そこで、すべての並び方を頂点とし、「見えている紙を 1 枚動かす手」を線とした表を最初に作っておき、注文ごとにこの表の上を幅優先探索して最短の手順を求める。 行き先の候補が複数ある時は、次の注文で手数が少なく済みそうな並びを選ぶ。

二つの方式の違い

補充の紙は「色の模様ごとに紙を 1 枚用意する」方式で、担当する模様の数だけ紙が要る。 順序の紙は「数枚の紙の並べ方で模様を作る」方式で、紙 s 枚の並べ方は s! 通りある。 最終版の順序の紙は 6 枚（並べ方は 720 通り）で、内容窓 38 個を 15 本の辺に割り当てている。

1 注文あたりの手数は、この置き換えで大きくは変わっていない。 共有の型紙で出す注文 1 件の手数は、置き換えの前後で 13.2 手から 12.7 手だった（間にほかの変更も入っている）。

効いたのは、紙の枚数が浮いたことである。 補充の紙 28 枚が、順序の紙 6 枚と、順序の紙の上に置く 1 窓だけが不透明な紙 1 枚になり、浮いた 21 枚を型紙に回した。 全商品を型紙に載せるので、型紙が 1 枚増えると共有の組が 1 組減る。 共有の組は 92 組から 71 組になり、共有の型紙で出す注文の割合は約 72% から約 55% に下がった。 共有の注文は単独の注文より 1 件あたり約 3.4 手多くかかっていたので、その割合が下がった分だけ平均の手数が減った。 紙 1 枚の値打ちは別に測ってあり、紙を 6 枚増やすと 1 ケースあたり −228（1 枚あたり約 38）だった。

なお、順序の紙に至る途中には、内容窓をグループに分け、グループごとの色の向きを 11 枚の紙の重ね順で切り替える版を経ている。

設計フェーズの最適化

設計フェーズでは、順序の紙の割り当て表の候補を複数作り、それぞれを短い焼きなましで評価して 1 つを選ぶ。 選んだ割り当て表の上で、型紙の組の選び方と層の割り当てを、1 注文あたりの期待手数のモデルを目的関数にした焼きなまし法で決める。 このモデルの値の差は、実際の手数におよそ 0.9 倍で移ることを測ってある。

判定に近い速さの模擬で、設計フェーズの命令数を処理ごとに分けると、割り当て表の候補作りが 40%、候補を評価する短い焼きなましが約 20%、型紙の設計の焼きなましが 29%、制御窓の並べ順の最適化が 8% だった（設計フェーズの終わりが 1.15 秒だった時点の 1 ケースの測定）。 設計フェーズは時間で打ち切るので、速くするほど反復が増えて設計が良くなる。

注文フェーズの探索

注文フェーズでは、前の型紙を沈め、順序の紙を並べ替え、型紙を持ち上げ、制御窓を直す。 制御窓の修正は数手分の候補を探索する。 探索の終わりの並びは、手数に「次の注文以降にかかる手数の見込み」（以下、先の見込み）を足した値で比べる。 最後に、手順を短くする局所探索をかける。

注文ごとの時間は「残り時間 ÷ 残りの注文数」で決め、足りない時は探索の幅を段階的に絞る。 判定に近い速さの模擬では、注文の大半が最も広い探索で処理されていた。 出力の直前には判定器と同じ規則で手の合法性を確かめ、合わない手は作り直す[^guard]。

[^guard]: 途中の版で、約 1,200 ケースに 1 回、見えていない紙を動かす不正な出力が出ていたため。

点数の推移

判定の点が記録に残る 24 回の提出を並べる。 人間の分と AI の分は、前の提出からの判定の点の差を、その間に入った変更の中身の出どころで分けたものである。 変更の中身（案そのもの）が人間から来たものを人間の分とし、人間が方向だけを示して AI が中身を考えた変更は AI の分とした。 1 回の間に両方が混ざる時は、手元の測定の比で按分した。 順位は提出直後の With AI 部門の順位である。 最初の行は、人間が「1 bit ずつ操作するカード（i ビット目が 0 か 1、残りが穴）のリストを操作すれば、少なくとも全ての注文を処理できる」と方針を示し、AI が実装した最初の解法である。 判定の点が記録に残っていないので、手元の平均を括弧で書いた。

日付 1 ケースの平均 人間の分 AI の分 順位 主な変更
10⁄30 （手元 32,770） 最初の解法。人間が指示した、窓ごとに 1 bit ずつ色を切り替えるカードの方針（誤り 0）
10⁄31 16,670 66 記録に残る最初の判定
10⁄31 15,273 0 −1,397 71 共有の型紙、型紙の設計の焼きなまし
11⁄01 14,951 0 −322 76 型紙を沈める位置に、担当する商品の多さの項
11⁄01 14,167 0 −784 64 型紙を持ち上げた後に、手数の減る 1〜2 手を探す
11⁄01 13,449 0 −718 53 補充の紙
11⁄01 12,849 0 −600 40 補充の紙の詰め方、浅い層を補充の紙に、どける紙の置き場所の模擬
11⁄01 12,761 −88 0 不明 無駄な手を省く手順の見直し
11⁄01 12,644 0 −117 45 暗黙の決定の検証で見直した手順と窓の数
11⁄02 12,450 0 −194 52 取っ手の色の偏りの罰金、2 手の候補の拡大など
11⁄03 12,406 0 −45 69 覆われる制御窓へ沈める紙の色を多数派に
11⁄05 12,403 0 −3 89 設計の焼きなましの高速化、注文の時間の動的な配分
11⁄05 11,289 0 −1,114 35 順序の紙を中心とする構造の変更
11⁄05 10,955 0 −334 23 割り当て表の最適化、手順の局所探索など
11⁄06 10,910 0 −44 23 内容窓の数、制御窓の並べ順の改良
11⁄07 10,795 0 −115 19 順序の紙の上の 1 窓の紙、割り当て表の候補の作り直しなど
11⁄07 10,783 0 −12 18 手順の近傍の修正、高速化
11⁄08 10,770 0 −13 20 手順の近傍、設計と注文の時間配分、焼きなましの高速化
11⁄08 10,741 0 −29 20 先の見込みの項、手順の近傍、高速化
11⁄08 10,714 0 −27 17 隠れた型紙の行き先の選び直し、時間の上限 1.8 秒など
11⁄09 10,712 0 −2 20 先の見込みの重み
11⁄09 10,715 0 +3 21 手順の近傍
11⁄09 10,675 0 −40 18 先の見込みの層の項
11⁄09 10,668 0 −7 17 近傍の束ね、層の項の高速化
11⁄09 10,674 +1 +5 20 最終提出（時間の上限 1.85 秒、次点の手順への SH_V、層の項の重み、x86_64 での高速化）

50 ケースの判定の揺れ（版の比較で標準誤差 約 13）より小さい差は、どちらの分も意味のある大きさではない。 最後の行の +1 と +5 はこれに当たる。 11⁄01 の 12,761 の提出の順位は、提出の前後で変わらなかったことだけが記録に残っている。

どの工夫が点に効いたか

点への寄与を大きい順に並べると、構造の変更、探索の候補と近傍の拡張、評価の外れの修正、高速化と時間配分の順になった。 パラメータの調整はほとんど効かなかった。

構造の変更が最大だった

最初の 2 日で、手元の平均は 32,770 から 13,437 まで下がった（測り方は途中で変わっている）。 内訳は、取っ手つきの型紙で −4,635、型紙を層に分けた階段で −1,952、制御窓の専用の紙の廃止で −1,350、補充の紙で −568 などである（手元の測定）。

11 月 5 日の、順序の紙を中心とする構造の変更は、判定で 1 ケースあたり −1,114（12,403 → 11,289）と、コンテスト中で最大の一歩になった。 手元の測定では、補充の紙を、内容窓のグループごとに色の向きを切り替える紙に置き換えた最初の版で約 −370、順序の紙で −291 ± 15、割り当て表の最適化で −183 ± 20、前の型紙の沈め先を模擬で選ぶ規則で −100 だった。

その 3 日前（11 月 2 日）の分析では、補充の紙を使う構造のまま改善を積んでも 12,000 前後で止まる、という見積もりが出ていた。 順序の紙は、補充の紙が持っていた「穴を固定の色で覆う」役割を「並べ替えで色を選ぶ」役割に変えたことで、その見積もりの前提を外した。

探索の候補と近傍を広げる変更

順序の紙の直後の 1 日で、判定はさらに −335 下がった（11,289 → 10,955）。 効いたのは次の変更である（手元の測定）。

  • 順序の紙の割り当て表の焼きなましを、窓 1 つの選択肢をまとめて評価する熱浴法にした（−59）。
  • 制御窓の並べ順を、隣り合う窓の色の相関が大きくなるように決めた（−45〜−51）。
  • 注文の手順を短くする局所探索と、型紙の置き場所の計画し直しを加えた（それぞれ約 −36、約 −28）。
  • 割り当て表の候補を 3 本作って、短い焼きなましで選ぶようにした（−23）。

どれも、それまで「探索は飽和している」と見えていた場所だった。 実際には、候補の集合や近傍が狭く、目的関数が見ていない次元があった。 同じ時期の広いパラメータ探索は、−15 にとどまった。

評価の外れを特徴に回帰して見つけた項

最終日の最大の改善は、先の見込みに足した層の項である。 長い入力で 1024 注文あたり −41.0 ± 1.1、判定で 1 ケースあたり −40.4 だった。

この項は、重みの調整ではなく、評価の外れの分析から見つかった。 注文を 1 件だけ変えて、その先 16 注文を本番の手順で流し、先の見込みが予測した差と実際の差のずれを測った。 そのずれを終わりの並びの特徴に回帰すると、「層の 1 枚目の紙の色が、その層の多数派の色でない層の数」が大きく効いていた。 この数を先の見込みに重み約 0.3 で足したのが、この改善である。

重みには鋭い山があり、先の見込みの別の項（並びの乱れを数える項）の重み 0.3 をわずかに超えた所で効く。 二つの項の重みの大小で、どちらの並びを好むかが入れ替わるためと見ている。

高速化と時間配分は数点ずつ

結果を変えない高速化は、設計フェーズと注文フェーズの両方で何周も行った（ある 2 回の高速化だけで、注文の処理の命令数が約 0.65 倍になった）。 ただし点への効きは、1 回あたり数点にとどまった。 判定環境に近い速さの模擬では、ほとんどの注文が既に最も広い探索で処理されていたからである。

時間の上限は 1.7 秒から 1.8 秒、1.85 秒へ延ばした。 効果は 1.8 秒への延長で −1.9〜−3.5、1.85 秒への延長で −0.5〜−1.5 だった（手元の模擬、1 ケースあたり）。

効かなかったこと

次の方向は、大きく試して効かなかった。

  • 約 40 変数、42 変数、17 変数のパラメータの測り直しは、どれも既定値の近くで平らだった。
  • 数注文先までの先読みは、2 秒に収まらなかった。
  • 順序の紙で表せる組の制約（同じ辺の向きがそろうこと）を緩める 7 つの仕組みは、どれも改善の上限が 30 点未満だった。
  • 1 位との差の原因を独立に考えさせた 5 人の担当は、「今の構造は境界に近い」と診断した。 ただし 2 巡目の担当が、「下げる仕組みが見つからない」ことを「境界にいる」と読むのは推論の飛躍だと指摘している。

人間の貢献

人間は解法のコードを書いていない。 変更の中身が人間から来たものは、次の 3 つである。 どれも AI が実装と測定を行い、本線に入れた。

1 bit のカードという出発点（10 月 30 日）

人間は最初に「1 bit ずつ操作するカード（i ビット目が 0 か 1、残りが穴）のリストを操作すれば、少なくとも全ての注文を処理できる」という考えを出した。 AI はこれを実装し、誤り 0 の最初の版（手元で 32,770）ができた。 判定の点が記録に残っていない版なので、点数の推移の表には現れない。

例の中の無駄な手の指摘（11 月 1 日）

AI が解法の説明のために作った例に、「B1 をどけた後に B1 を沈める」という 1 手にまとめられそうな手があった。 人間はこれを見て「実際の挙動でも発生していますか？」と聞いた。 AI はコードを読んで、例のこの無駄は実際の解法では起きていないと答えたが、人間はさらに「全ての挙動をかぞえてくれ」と求めた。 AI は全注文の手を 1 手ずつ再生して数える道具を作り、別の種類の無駄な手（1 手だけ省いても表示が合う手と、同じ紙を 2 回動かす手）を 1 注文あたり約 0.1 手見つけた。 それを省く手順の見直しを入れて、手元の平均は 12,816 から 12,706 に下がった（−110）。 次の提出で、判定の点は 12,849 から 12,761 に下がった（−88）。 この間に入った変更は、これだけである。

時間の上限の延長（11 月 9 日）

人間は、時間の上限を 1.8 秒から 1.85 秒に延ばすと決めた。 手元の模擬で、判定に近い速さの 1 ケースあたり −0.5〜−1.5 だった。

AI の貢献

AI は解法のすべてを実装した。 上の 3 つ以外の改善は、どれも中身を AI が考えた。 そのうちいくつかは、人間の指示がきっかけになっている。

Claude と Codex の稼働時間

コンテストの期間（10 月 30 日 22:14 から 11 月 9 日 19:00 まで、236.8 時間）の作業の記録から、Claude と Codex が動いていた時間を数えた。 記録の書き込みの間隔が一定の長さ以内の時間を稼働とみなし、それより長い空白（長いコマンドの待ちや停止）は除いた。 区切りの長さで値が変わるので、10 分、30 分、60 分の 3 通りで数えた。

延べの時間（並列に動いた担当を別々に足す） 実際の時間の長さ（どれかが動いていた時間）
Claude 370〜461 時間 132〜151 時間
Codex 2.4〜3.4 時間 2.3〜3.3 時間
  • Claude の延べ 370 時間（区切り 10 分）のうち、267 時間はサブエージェント（並列の担当）、103 時間は親のセッションと別に立てたセッションである。 実際の時間の長さ（132〜151 時間）は、コンテストの期間の 56〜64% に当たる。
  • Codex の記録は 4 セッションで、大半は人間が別に動かしたセッション（Codex に解法の案を聞いたもの）である。 ほかに Claude が 10 月 31 日に Codex に頼んだ調査が 2 回あるが、Codex 側に記録が残っておらず、数に入っていない（Claude の記録では、それぞれ数分で終わっている）。
  • 間隔が区切り以内なら、人間の発言を待つ時間も稼働に含まれる。

紙の構造

紙の構造は、すべて AI が考えた（数字は手元の測定）。

  • 型紙と制御窓（−4,635）。 きっかけは人間の 2 つの依頼である。 一つは「注文順が事前にわかっていたら、見えていない紙も操作できたら、…どれくらい理論値が変わるのか研究してください」という依頼で、AI の調査は「見えていない紙も動かせるなら、商品のバーコードを全面に写した紙で 16,533 まで下がるが、実際の規則では使えない」と結論した。 もう一つは「過去の AHC のメモを調べて、サブエージェントで実験して」という指示で、AI はこれを受けて 3 つの実験を並列に始めた。 そのうちの 1 つが、調査の結果と、AI 自身の小規模の厳密計算（紙 8〜9 枚の小さな問題で、商品に合わせた穴あきの紙の重ね順を組み替える設計が 1 bit のカード方式より 44〜57% 少ない手数）をもとに、型紙に取り出し用の窓（制御窓）を持たせる形を作った。
  • 制御窓の専用の紙の廃止（−1,350）と、型紙を層に分けた階段（−1,952）。
  • 共有の型紙（−306）。 人間の「ぜんぜん違うアプローチの探索に時間を使ってください」を受けて AI が始めた 4 つの探索の 1 つから出た。
  • 補充の紙（−568）。
  • 順序の紙（判定で −1,114）。 人間が「小手先の改善では到達できないことがわかっているため、大方針レベルで探索せよ」という目標を置き、AI がその日のうちに考えた。
  • 順序の紙の上の 1 窓だけが不透明な紙（−29〜−42）。

注文の手順の探索

  • Codex の案を試す過程で見つけた工夫。 人間が別のセッションで Codex に「13.5 手以下まで改善できる可能性がある手法は残っているか？」と聞き、その答えの 3 つの案を貼り付けた。 AI は 1 つ目（掘り出しでどける紙の置き場所と制御窓の修正を一緒に計画する）を担当に試させた。 案そのものの探索は −3 手程度だったが、担当は途中で次の工夫を見つけた。 紙を沈める位置に担当する商品の多さの項を足す（−312）、型紙を持ち上げた後に手数の減る 1〜2 手を探す（−812）、修正の手を選ぶ時に次の注文の掘り出しの増え方を罰金にする（−33）、である。 案の 1 つ目そのもの（どける紙の置き場所を、注文の残りの模擬で選ぶ）も、後に別の担当が実装した（決定的設定の 30 ケースで −88.5）。
  • 暗黙の決定の検証。 人間の「実験をせずに暗黙に意思決定した部分をリスト化し、全てを実験してください」を受けて、AI が 22 項目を洗い出して実験した。 注文の手順の 3 項目（決定的設定の 100 ケースで −49.5）と、内容窓と補充の紙の枚数の選び直し（同じく −66.5）を採った。
  • 探索の候補と近傍の拡張。 順序の紙の後の改善の大半は、並列の担当が探索の候補と近傍の制限を一つずつ外して得た。 割り当て表の最適化、制御窓の並べ順、手順を短くする局所探索、型紙の置き場所の計画し直し、割り当て表の候補の複数化（合わせて判定で −334）、持ち上げる前に隠れる紙を動かす候補（決定的設定で −94）、隠れた型紙の層の中での行き先の選び直し（長い入力で −11）などである。

評価の外れの分析

最終日の最大の改善（先の見込みの層の項、判定で −40）は、AI の分析から見つかった。 注文を 1 件だけ変えた時の先の見込みの予測と実際の差を、終わりの並びの特徴に回帰する、という分析である。

最終版に入った、色の偏りの大きい層だけ層の項を重くする変更（長い入力で 1024 注文あたり −1.82）は、人間の指示した進め方（サブエージェントへの課題文に親の AI の案を書かず、複数の担当に同じ問いだけを渡し、1 人だけが出した案も重く見る）で立てた担当の 1 人が見つけた。

小さな改善を見分ける測り方

11 月 7 日以降の改善の多くは、1 つあたり 1 ケース数点だった。 判定の 50 ケースの揺れ（版の比較で標準誤差 約 13）より小さいので、判定の点では見分けられない。 AI は、手の列を固定する決定的設定、注文を 8,192〜32,768 件に伸ばした長い入力、命令数を時計にして判定に近い速さを再現する模擬を作り、これらで数点の改善を確かめて積み上げた。 判定の点は、この間に 10,795 から 10,668 まで下がった。

今後も使えそうな指示

人間の指示のうち、その後の記録で点への効き目を確かめられたものを挙げる。 どれも、何を作るかではなく、何を調べるか、どこまで探すかを指示したものである。

  • 規則を緩めた時の理論値を調べさせる。 「注文順が事前にわかっていたら、見えていない紙も操作できたら、…どれくらい理論値が変わるのか研究してください」という依頼で、全面に模様のある紙は強いが、見えている紙しか動かせない規則が障害だと分かった。 この見立てから、取り出し用の窓を持つ型紙が生まれた（手元で −4,635）。
  • 推論で答えさせず、実際の挙動をすべて数えさせる。 例の中の無駄な手について、AI は「実際の解法では起きていない」と推論で答えたが、「全ての挙動をかぞえてくれ」で数え直させると、別の種類の無駄な手が 1 注文あたり約 0.1 手見つかった（手元で −110、判定で −88）。
  • 実験せずに決めたことを列挙させ、すべて実験させる。 「これまでの回答の中で、実験をせずに暗黙に意思決定した部分をリスト化し、それぞれに対して考えられる全てを実験してください」で、AI は 22 項目を洗い出し、2 件を採った（決定的設定で −49.5 と −66.5、次の提出で判定 −117）。
  • 行き詰まった時は、方針の水準での探索を目標に置く。 「小手先の改善では到達できないことがわかっているため、大方針レベルで探索せよ」という目標の下で、AI は同じ日のうちに順序の紙に至った（判定で −1,114）。 その 3 日前に AI の分析は「今の構造のままでは 12,000 前後で止まる」と結論していて、目標を下げずに探す範囲を広げさせたことになる。 「ぜんぜん違うアプローチの探索に時間を使ってください。サブエージェントに探索させてもよいです」からも、共有の型紙が生まれた（手元で −306）。
  • アイデアの探索では、サブエージェントへの課題文に親の AI の案を書かせず、同じ問いだけを複数の担当に独立に考えさせる。 ふだんのサブエージェントは、親が方向を決めて渡していた（例えば「設計の段を、結果を変えずに速くする」）。 アイデアを探す時だけは、親は仮説や候補の案、「この観点で」といった誘導を課題文に書かず、全員に同じ問いと事実だけを渡す。 担当は互いの考えを見ずに考え、親はまとめ役として、1 人だけが出した案も多数の案と同じくらい重く見る。 親の案を渡すと担当の考えがそこへ寄るのを避けるための進め方である。 最終日にこの形で立てた担当の 1 人が、最終版に入った変更を見つけた（長い入力で 1024 注文あたり −1.82）。 ただし、この形で立てた担当の多くは、採れる変更を出していない。

おわりに

解答は、人間が示した 1 bit のカードの方針（手元の平均 32,770）から始まり、最終提出で 1 ケースあたり 10,674 になった（コンテスト終了時点で With AI 部門 22 位）。 点の大部分は紙の構造の変更から来た。 中でも、共有の型紙の穴を「模様ごとに 1 枚の紙」から「数枚の紙の並べ方」で埋めるように変えたことで紙が 21 枚浮き、判定の点で 1 ケースあたり −1,114 と最大の一歩になった。

変更の中身で数えると、判定の点の改善はほぼすべてが AI の分である。 AI（主に Claude）は、実際の時間で 132〜151 時間、並列の担当を別々に足すと 370〜461 時間動いた。 人間が決めたのは、何を調べさせるか、どこまで探させるかだった。 型紙も順序の紙も中身は AI が考えたが、どちらも人間が理論値の調査や方針の水準での探索を求めた後に生まれている。 人間の指示は、AI が自分では選ばなかった調べ方や探す範囲を持ち込む形で効いた、と見ている（解釈）。

最後の日の分析では、先の見込みの外れは、層の 1 枚目と 2 枚目が同じ色になる組に集まっていた（1024 注文あたり約 3.7）。 ただ、手数を足さずにこの組を直せる注文は少なく、コンテスト中には点に結びつけられなかった。