※ AIに（略）
入黄した
— ボンド@競プロ (@bond_cmprog) February 1, 2026
Bondo416さんのRECRUIT 日本橋ハーフマラソン 2026冬（AtCoder Heuristic Contest 060）での成績：11位
パフォーマンス：2728相当
レーティング：1816→2004 (+188) :)
Highestを更新し、初段になりました！#AtCoder #RECRUIT日本橋ハーフマラソン2026冬（AtCoderHeuristicContest060）
概要
N=100 頂点のグラフ上に K=10 のアイスクリームショップと 90 本のアイスクリームの木がある。頂点 0 から出発し、木でアイスを収穫してコーンに積み上げ、ショップに納品する。各ショップの在庫は集合（重複なし）で管理され、全ショップの在庫数の合計を最大化したい。木は初期状態ではすべてバニラ（W）だが、ストロベリー（R）に変換できる（不可逆）。最大 T=10000 ステップ。
方針
ビームサーチで各ステップの行動を決定した。
チャンク単位のビームサーチ
T=10000 ステップ全体を一度にビームサーチするのはメモリ的に不可能なので、CHUNK_SIZE（≈30）ステップごとに区切って計画する。各チャンクでビームサーチを実行し、最良パスを確定させて次のチャンクに進む。
状態表現
ビームの各状態は以下を持つ。
cur,prev_node: 現在位置と直前の位置（移動制約のため）cone_hash,cone_len: コーンの内容をローリングハッシュと長さで管理is_vanilla[2]: 各木がバニラかストロベリーかを 128bit のビットセットで保持score_delta: そのパスで得た新規納品数convert_count,turns_since_convert: 変換回数とクールダウン管理
評価関数
ビームの選別に使う評価関数は複数の要素の重み付き和で構成した。
| 要素 | 重み | 説明 |
|---|---|---|
| 新規納品数 | W_DELIVERY=40000 | 確定スコアへの寄与（最重要） |
| ショップへの距離 | W_DIST=170 | コーンを持っているとき、最寄りショップへの距離が近いほど高評価 |
| コーンの長さ | W_CONE_LEN=60 | 長い文字列ほど多様性に寄与しやすい（上限6） |
| 新規性ボーナス | W_NOVEL=3500 | 現在のコーンが最寄りショップで未納品ならボーナス |
| 重複ペナルティ | W_DUP=500 | 既に納品済みの文字列を持っている場合のペナルティ |
| 次数ボーナス | W_DEGREE=40 | 分岐の多い頂点を好む |
| ノイズ | EVAL_NOISE=300 | 探索の多様性を確保するランダムノイズ |
新規性チェック
納品時に「その文字列が本当に新しいか」を正確に判定する必要がある。グローバルの FlatHashSet（ショップごとの在庫管理）に加えて、ビームの親チェーンを遡って同じチャンク内で先に納品された文字列との重複も検出するようにした。
適応的ビーム幅
各チャンクの実行時間を計測し、時間に余裕があればビーム幅を広げ、時間が足りなければ狭める。これにより制限時間（2秒）をギリギリまで使い切る。
木の変換戦略
全 90 本の木のうち半分（45本）をストロベリーに変換する。変換はクールダウン（T / 変換上限 ≈ 222ステップ間隔）を設けて均等に分散させた。これにより序盤はバニラ系の文字列を集め、徐々にストロベリー混じりの文字列も生成できるようになる。
高速化
- FlatHashSet: オープンアドレッシングの自作ハッシュセットで O(1) の挿入・検索
- ローリングハッシュ: コーン文字列の比較をハッシュ値の比較に置き換え
- CSR 隣接リスト: キャッシュ効率の良いグラフ表現
- BFS 前計算: 全点間最短距離と各頂点から最寄りショップへの距離を事前計算
- 出力バッファリング: 200KB バッファに書き溜めて最後に一括出力
ハイパーパラメータ調整
Optuna で評価関数の重みやビーム幅を探索した。50 試行の TPE サンプラー + MedianPruner で以下の値に落ち着いた。
| パラメータ | 値 |
|---|---|
| BEAM_WIDTH | 1700 |
| CHUNK_SIZE | 30 |
| W_DELIVERY | 40000 |
| W_DIST | 170 |
| W_CONE_LEN | 60 |
| W_NOVEL | 3500 |
| W_DUP | 500 |
| W_DEGREE | 40 |
| EVAL_NOISE | 300 |
ビジュアライザ
#AHC060 #rcl_procon
— ボンド@競プロ (@bond_cmprog) February 1, 2026
GeminiにパワハラしてClaude Codeに無限残業させた
Seed = 0
Score = 1165 pic.twitter.com/3FeMyuULnI
やらなかったこと / 試さなかったこと
- Chokudai Search: 制限時間いっぱいビームの深さを伸ばし続ける方式。チャンク分割より柔軟だが実装が間に合わなかった
- パス列挙による計画: 「ショップ→木→…→ショップ」のパスを BFS で列挙し、新規文字列を生成するルートを明示的に計画する方式
- 変換タイミングの最適化: 変換する木の選択や順序を評価関数に組み込んで最適化すること
- ショップ間の分担戦略: 各ショップに異なる文字列セットを割り当てて効率的にスコアを稼ぐ戦略
感想
- 最初は貪欲 + ランダムプレイアウトで実装したが、スコアが伸びずビームサーチに切り替えた
- 評価関数の設計が肝で、新規性ボーナスと距離ペナルティのバランスが重要だった
- LLM にビームサーチの骨格や高速化テクニックの実装を手伝ってもらった
- Optuna でのパラメータ調整は安定した改善をもたらしたが、劇的な変化はなかった
- ローカルでの最終スコアは 100 ケース平均 1139 点
