AtCoder Heuristic Contest 066 に参加したので記録しておく。
結果
今回はケースごとの順位の相対スコアの和という方式。参加者約1200人で333位だった。performance 1594でそんなに良くなかった。
問題概要
グリッド状のマス目に、M個のボールとM個のかごがある。
1ターンに、上下左右の移動、交換(手持ちのボールを置き、その場所にあるボールを拾う)、マクロの記録開始・終了、マクロの再生のいずれかができる。
操作列を一つだけマクロとして記憶することができ、使用すると、記憶した操作列を再生する。ただし操作列の長さがTを超える場合は無視される。
全てのボールを拾ってかごまで戻したい。操作列をできるだけ短くせよ。
実装内容
- ほぼClaude Codeが実装
- ざっくり、経路を決めてからマクロを決める
- 400msくらい使い、適当なマクロを使い、訪問順序を焼きなます
- 残りの時間は、使用するマクロを粗いコストで評価して、小さいものから真のコストを評価して最短を採用する
- (変数がたくさんあってめちゃ複雑だが省略)
生成AIによる途中経過の分析
- リーダーボードとの差分によると、ほぼ一様に15%くらい負けている
- 構造解析: 出力ボタンの 62.7% が一回限り単独リテラル(F/R/L)、P は実行opの81.5%を28.2%のボタンで処理。S=14.7%は削減不能
- 単一マクロ制約が非常に強く、マクロをさらに圧縮することは困難
- 今のアルゴリズムの出力は最適であり、これ以上縮める余地はない
終了後、振り返り
他の方の結果を見ると、マクロを決めて焼きなますほうが効果的だった。
自分の最初の指示も、「直進+右折+直進など、固定パターンをいくつか用意して、焼きなましにより、パターン毎に解を生成し、最終的に一番良いものを選ぶ」というもので、なんとなくマクロも焼きなますイメージはあった。
試行錯誤の結果、得られたものとしては、経路を焼きなましてからマクロを選ぶというものになり、85点くらい取れる感じのものができあがった。
全体の流れを作り直す必要があり、何回か試行したが、以下の2点でClaude Codeとの会話がうまくいかなかった。
- 全体の流れをリセットしてやり直す指示として伝わらず、部分だけ差し替える実験 (例えば、前半が差し変わるが、後半の関数がそのままだったり、同じディレクトリにあるファイルを参考にして実装されるなど) が行われて棄却される
- 全く新しい解法では初動70点くらいしか取れず、85点のものと比べてしまい棄却される
どういう指示出しをすれば良かったのかClaude Codeに聞いたところ、全体をやり直すには以下の4要素で指示せよとのことだった。(opusはこういうmemoryを自動生成してくれる)
- 既存のコードを「置き換える」か「拡張する」か
- 主要な探索手法
- 評価器 (新規なのか既存のパイプラインなのか)
- 何から何を導出するか (例: マクロからルートを導出する)
また、全体をやり直した場合には、既存の実装との比較ではなく、変化率や上界など、別の指標で評価するべきだということもわかった。
ということで次回はもう少しうまくやれそうな感触を得た。