AHC069 参加記
私です。
RECRUIT Nihonbashi Half Marathon 2026 Summer（AtCoder Heuristic Contest 069）に参加しました。
問題
今回の 問題 は、50 × 50 の公園に、順番にやってくるピクニック客を配置するというものでした。
公園の各マスは芝生か池になっており、グループを受け入れる場合は、人数と同じ個数の連結な芝生マスを割り当てます。
領域の面積を 、周長を とすると、コンパクト度は
となります。
正方形に近いほどコンパクト度が高く、もらえる利用料も高くなります。
一方で、目の前のグループを何でも受け入れていると、空き地が細切れになり、後から来たグループを置けなくなります。
さらに、すでにいるグループをお金を払って移動させることもできます。ただし、一度でも細長い場所へ移動させると、その悪いコンパクト度が最後まで残ります。
つまり、
- どのグループを受け入れるか
- どんな形で置くか
- どこに置くか
- いつ既存のグループを移動させるか
を、未来の入力がわからない状態で決める問題です。
最初の方針
最初は、人数ごとに正方形や長方形に近い形をたくさん作っておき、置ける場所を探す方針にしました。
同じ周長の候補が複数ある場合は、公園の端・池・すでに使われている領域に接するものを優先します。
空き地の真ん中に置くと領域を分断しやすいので、なるべく端から詰めて、広い空き領域を残そうという発想です。
また、周囲のグループがすぐ帰ってしまうと、せっかく端に寄せても壁が消えてしまいます。そのため、長く滞在するグループとの接触を高く評価しました。
整ったテンプレートを置けない場合は、空き領域の中から連結な マスを育てて、境界のマスを入れ替えながら周長を短くしました。
このあたりは、かなり素直な「コンパクトな形を端から詰める」貪欲です。
受け入れるグループを選ぶ
置けるグループをすべて受け入れると、かなり早い段階で公園が埋まってしまいました。
そこで、各グループについて
を計算しました。
これは、ざっくり言うと「芝生1マスを1時間使わせたときに、どれくらい利用料をもらえるか」です。
直近のグループの密度を記録しておき、混雑しているときほど高密度なグループだけを受け入れます。逆に、空いているときや終盤では基準を緩めます。
単純な式ですが、配置方法だけを頑張るより、誰を断るかを考えた方がずっと効きました。
移動
今回の面白いところは、すでにいるグループを移動させられることです。
通常の配置ができないとき、理想的な配置場所を塞いでいるグループを一度どかし、新しいグループを置いた後、どかしたグループを別の場所へ詰め直します。
移動費係数 R が小さいケースでは、1組や2組だけでなく、玉突きのような連鎖再配置も試しました。
ただし、移動すれば得をするとは限りません。
となる場合だけ採用しました。
それでも2秒以内に1,000グループを処理する必要があるため、残り時間に応じて探索量を落とし、最後は必ず合法な出力を返すようにしました。
Codexに改善してもらう
ここからが今回の本題です。
最初の100ケース平均は約 45.47M でした。そこから、Codexと「固定500ケース平均 75M を超える」ことを目標に、改善を進めることにしました。
改善は、次の流れで進めました。
- 次に試す仮説を1つだけ決める
- 実装前に、期待する効果と棄却条件を決める
- 固定100ケースで一次評価する
- 良さそうなものだけ固定500ケースへ進める
- 固定500ケースで改善した変更だけ残す
- 失敗した変更だけを撤回する
また、戦略を考える役、実装する役、結果を集計する役、実験を疑う役も分けました。
実験結果が返ってくるたびに一応目を通し、理解できているか怪しいまま、とりあえず Yes と返して次の実験へ進めてもらいました。
初日は、ほぼ休みなく小さな変更と評価を繰り返し、45M → 59M → 63M → 69M と伸びていきました。最終的な正式ベストは、固定500ケース平均で約 73.36M でした。
まぁ、残念ながら目標の 75M には届かったのですが。
うまくいったこと
それでも、最初の 45M から 73M までは伸びています。中でも、特に効いた変更をいくつか挙げます。
一番わかりやすかったのは、配置可能な場所の列挙をビット演算で高速化したことです。探索の賢さを直接変えたわけではないのですが、同じ2秒でも後段のフォールバックや再配置までたどり着けるようになり、固定500ケース平均が約 +139k 上がりました。
また、移動費が安い場合の連鎖再配置では、最初に見つけた1つの置き場所だけでなく、邪魔になるグループの組み合わせが異なる候補を3つまで試すようにしたことで、さらに約 +109k 改善しました。
ほかにも、グループの面積を考慮した受入制御、残り滞在時間に応じた接触評価、池の多さによる方針の切り替えなど、局面に応じた小さな変更が少しずつ残りました。
最終的に効いたのは、すごい未来予測というより、「コンパクトに置く」「空き地をまとめて残す」「安いときだけ動かす」「探索を速くする」といった地道な改善の積み重ねでした。
やはり高速化…高速化が世界を救う！
うまくいかなかったこと
実験を続けていると、100ケースでは良いのに500ケースでは悪化する変更がたくさん出てきました。
例えば、孤立した1マスの空き地を減らす、探索候補を増やす、大きなグループ向けに空間を予約する、といった案です。
どれも説明だけを聞くと良さそうなのですが、別の場所への接触を壊したり、探索時間を使いすぎたり、受け入れられたはずのグループを断ったりして、全体では負けました。
「盤面を良くしたように見える」と「最終スコアが上がる」が全く別なのがまた腹が立ちましたね。
空き領域を広くしても、そのために高価なグループを1つ逃せば負けます。候補をたくさん調べても、探索が少し遅くなって後半の行動が変われば負けます。
やっぱりAHCむじ〜〜〜。
オフラインなら見えるもの
終盤は、CodexやGPTに言われるがままに、「未来が全部わかっていたら、どれくらい改善できるか」を調べる実験もしました。
その中で、実際には安全に置けたのに断っていたグループを、未来の配置と衝突しない場所へ追加する実験では、100ケースすべてで改善し、平均約 +824k の余地が見つかりました。
つまり、配置できる場所がないことよりも、受け入れ判断の偽陰性がかなり残っていました。
ただし、その安全な場所が本当に最後まで空いているかは未来を見ないとわかりません。現在までの情報だけで予測しようとすると、うまく識別できませんでした。
「改善余地がある」ことと「オンラインで改善できる」ことも、やはり別物でした。
最後に
正直なところ、後半1週間でのスコアはほっとんど変わっていないと思います。なんなんだ。AHCお前は一体。
とはいえ、私も開始から2日ぐらいはだいぶ上位にいたんですよ？
あれ、本当に何をしていたんだ…？
あとはなんだろ。そうだな。今回のAHCは割と観戦がめっちゃ楽しかったですね。興奮してるのがツイートの内容から見えると思います。
さて、現在、暫定テスト終了時点では136位で、レートも100以上増える見込みです。ただし、AHCはシステムテストで順位もレートも大きく変わるので、まだ喜んでいいのかはわかりません。
ひとまず、システムテストで爆発していないことを祈ります。
それでは、また。
最後の最後に
レート変動が来た時間軸の私です。
順位が下がりました。うんこ。
また黄色パフォも逃したしさぁ。はぁ。またお預けですわ。
まぁ、100いくつは上がったからいいんですけど。
LLMに任せずもっと頭を働かせないとな、と思った私でした。それでは。