- 0.はじめに
- 1.問題文の概要
- 2.ビジュアライザ
- 3.生成AIの話
- 4.解法（得点677081394まで）
- 5.解法（得点777230596まで）
- 6.やめた解法(ビームサーチ)
- 7.さらなる改善（得点811591192まで）
- 8.ラスト1時間（得点856800493まで）
- 9.最終結果
- 10.終わりに
- 11.おまけ：AHCラジオ
0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴5年11か月のかえでです。
これは、2025年11月29日土曜日15時から19時までの4時間に開催された「AtCoder Heuristic Contest 057」の参加記になります。
結論を先に書くと、701人中4位、パフォーマンス3055を取りました。その結果、Heuristic Ratingは2202になり、入黄しました。
正直なところ、この結果に自分自身も驚きを隠せません。きっとこれを読んでくださっている方も同じ気持ちだと思うので、できるだけ丁寧にコンテストの振り返りを書きたいと思います。
1.問題文の概要
- 目的
- N=300 個の原子を、時刻 t=0 からt=999 の間に操作し、最終的に10個の分子（それぞれ原子30個を含む）を作り上げる。その過程でかかる結合コスト（距離の総和）を最小化する。
- 環境・ルール
- 盤面:L×L (100000×100000) のトーラス平面（上下、左右がつながっている）。
- 原子: 初期位置と初期速度を持つ。
- 移動: 毎時刻、原子（または結合した分子）は現在の速度に従って移動する。
- 結合:任意のタイミングで異なる連結成分同士を結合できる。
- コスト: 結合時の2点間の距離（トーラス距離）。
- 速度更新: 結合すると、運動量保存則（重み付き平均）に従い新しい速度になる。
- 制約: 最終的に M=10 個の連結成分、各サイズ K=30 でなければならない。
2.ビジュアライザ
問題文の「例を見る」リンクからビジュアライザを見ます。色とりどりの原子がつながっていく様子がわかりました。辺の長さを短くすることを考えれば良いのだなあと思います。
3.生成AIの話
前回のAHC056まではChatGPTを使用していたのですが、こちらの指示に対して「できない」と意図が全く異なるコードを頻繁に返してきたことに辟易したので（とはいえ、もちろん自分の実装力より上なのですが…）、今回のコンテストではGeminiを使用することを最初から決めていました。この文章の中で生成AIと書いた場合、それは Gemini 3 Pro Preview を指します。
なお、AHCでは1回ずつ質問を投げかけるような通常の生成AIの利用については禁止されていません。
AtCoder Heuristic Contest 生成AI利用ルール - 20250616版 - AtCoderInfo
4.解法（得点677081394まで）
問題文を読ませた後の、生成AIからの最初の解法提案です。
---（ここから）---
- 解法の指針（アプローチ）
この問題は「動的クラスタリング」と「スケジューリング」の組み合わせです。制約（10個×30原子）が厳しいため、闇雲に結合すると詰みます。以下のような段階的なアプローチが有効です。- 1. グループ分け（パーティショニング）
最終的にどの原子が同じ分子になるかをあらかじめ決めてしまう方針が安全です。
N=300 個の原子をK=30 個ずつ M=10 のグループに分割します。 - 2. グループ内での結合戦略
グループが決まったら、各グループ（30個の原子）をどう繋ぐかを考えます。これは各グループ独立に計算できます。- 戦略A：貪欲法（Greedy）
シミュレーションを進めながら、「ある閾値以下の距離」に近づいたペアがいれば結合する。
結合すると速度が変わるため、再計算を行う。 - 戦略B：グラフ探索（MST / Steiner Tree）
原子をノード、結合をエッジとみなす。 - 「原子i とj が時刻t に結合する場合のコスト」をエッジの重みとする。
- ただし、結合すると軌道が変わるため、静的なグラフ問題には落とし込めません。「今の軌道で最も早く安く出会うペア」を優先的に処理する方針になります。
- 戦略A：貪欲法（Greedy）
- 3. 速度制御の重要性
結合による速度変化（平均化）を戦略的に利用します。- 速度を殺す: 逆方向の速度を持つ原子を結合させると、分子の速度は0に近づきます。特定の場所に「待機」させたい場合に有効です。
- 速度を維持する: 同じ方向の原子を結合させると、移動能力を維持したまま他の原子を「迎えに行く」ことができます。
- 4. 高度な改善（山登り法・焼きなまし法）
初期の解（結合手順）を作った後、以下のような操作で改善を試みます。- 結合順序の変更: AとBを先にくっつけるか、BとCを先にくっつけるかを変える。
- メンバーの交換: グループ1の原子Xと、グループ2の原子Yを入れ替えてみる。
- 推奨される初期実装ステップ
- 入力の可視化: 公式ツールのビジュアライザを見て、原子がどう動くか確認する。
- 固定グループ化: 座標 (x,y) だけで K-means を行い、10グループを作る。
- 単純待ち伏せ: グループ内で、最も距離が近くなる時刻 t を全ペア探索し、最もコストが低いペアから順に結合を予約していく。
- 更新: 結合が発生したら、その分子の新しい軌道を計算し直し、以降の結合計画を更新する。
- 1. グループ分け（パーティショニング）
---（ここまで）---
次のプロンプト
C++でプログラムを書きます。
・固定グループ化: 座標(x,y)だけで K-means を行い、10グループを作る。
・戦略A：貪欲法（Greedy）シミュレーションを進めながら、「ある閾値以下の距離」に近づいたペアがいれば結合する。結合すると速度が変わるため、再計算を行う。これを実行して結果を見たいです。デバッグ出力をつけてフルコードのプログラムをください。
このとき考えていた見通し的な話を追加すると、決め打ちすると、良いか悪いかの判断をしやすそうという気持ちでいました。とにかく「良い状態」が何かを知りたかったのです。
出力されたプログラムを実行してビジュアライザを見ます。
これを提出すると、得点485,364,218を得られます（本番552位、パフォ923）。
※コンテスト時には提出していないので、コンテスト後に提出をして確認をしました。
私は何をしていたかというと、ビジュアライザを見ていました。
ビジュアライザをよく見ると、原子の色は最終的に結合される分子の色になっているようでした。色の点が集まっていく様子を見つめます。ターンの途中では結合があまり行われず、最後に無理やり10個になるよう、原子を結合しているようでした。最後の何ターンかで、遠い位置の原子が結合され、スコアが悪化しているのがわかりました。結合の際の閾値を調整します。
閾値を変えるだけで、かなりスコアが変動することがわかりました。seed0だけで結果を見ていましたが、pahcerに切り替えて100テストケースを試すことにします。閾値の良さそうな値を探します。seed0ではスコアが3760237になりました。
最終的にプログラムの閾値を下記に変更したものを提出します。
- before
// t=0 で閾値 1000, t=800 で閾値 50000, t=950以降は無限大(強制結合)
double threshold = 2000.0;
// 時間経過ブースト
threshold += (double)t * 5.0;
- after
double threshold = 20000.0;
threshold += (double)t * 5.0;
100テストケースの平均は3851596で、150テストケースの予想は577739327でしたが、提出すると579122549になり、3位のスコアが出ました。（このまま終了すると、本番500位、パフォ1049になります）
コンテスト開始から15分ほど経過したところでした。
次の改善です。
ビジュアライザを見ていると、下図のような結合をしていました。
プログラムでは代表点を持っていて、代表点どうしを結合していました。そこで、結合する際は、AグループとBグループのペアの距離を全探索して、一番コストが小さくなる原子どうしを結合するように変更します。
プロンプト
連結する際、いちばんコストが最小となる頂点どうしをつなぎたいです
生成AIの返してきたプログラムを提出すると、得点563,706,322を得られます。私は本番時は提出していないので、コンテスト後に提出をして確認しました。これは本番511位相当、パフォ1021の得点になります。
このプログラムも閾値を調整します。100テストケースの平均は、4990になりました。プログラムを提出をすると、得点673,286,283を得ました。順位は38位でした。
seed0のスコアは、4463488まで上がりました。ビジュアライザを見ると、何点かの原子が最後まで浮遊していたり、最後に遠いグループどうしを連結して、スコアを悪化させているのがわかります。
プロンプト
どこにも連結していない原子が残り10個になったら、このターン以降Ｔターンまでの間に、まだ30点集まらないグループと距離10000以内に出合った場合、どのタイミングで、どのグループに出合うかを計算し、いちばんコストが低くなるタイミングでそのグループと連結するように変更します。
「残り10個」とか「距離10000」といった値は適当で、後で変更して何パターンか試そうと思っていました。未来予測機能（Look-ahead）が追加されます。
生成AIの返してきたプログラムを提出すると、得点563,706,322を得られます。私は本番時は提出していないので、コンテスト後に提出をしました。本番511位相当、パフォ1021となります。先ほどとスコアは変わっていませんでした。
プロンプト
将来的にどの30個が同グループになるかを最初に振り分けてください。
それでおおよそのスコアを推測します。実際は連結により進行方向が変わるので、今の概算よりもスコアがよくなるなら、近い頂点を仲間にし、グループのふりわけを変更するといった方針を取りたいです
（小さくなるだけではなく、残ったものと別のものが連結されたときのコストを推測するフェーズを入れるということです）
最初のグループ決めの際、最初にK-means法（座標のみ）で初期解を作り、ランダムで2つのグループから原子を1個ずつ選んでswapする山登りを0.8秒間行います。
戻ってきたプログラムを提出すると、得点562291741を得ます（自分は提出していないのでコンテスト後に提出しました）。
ビジュアライザを見て、原子の結合の条件が厳しい（なかなかグループに結合されない原子が最後まで多く残る）と感じました。
プロンプト
距離1万以内のものは最初に全て連結して良いです
生成AIから返されたプログラムを提出すると得点665872848を得ます。（コンテスト時は提出していないため、コンテスト後に提出をして確認しています。これは本番412位相当、パフォ1236の得点になります。）
プロンプト
2個以上のグループが10になった時点で、それ以上は原子と10グループの分子のみの形で連結を進めてください
生成AIから返されたプログラムを提出すると得点665795159を得ます。（コンテスト時は提出していないため、コンテスト後に提出をして確認しています。これは本番412位相当、パフォ1236の得点になります。先ほどと変わっていないですね。）
ビジュアライザを見ていたのですが、グループ数を10より増やさないことが、思ったより良くならないと感じました。（コンテスト後には他の方の解法で、10グループ固定の解法をいくつか見たので、これを詰める方法もあったのかもしれません）
そこで、この方針を追うのはやめて、今のチャットを終了し、新しいチャットに切り替えました。
5.解法（得点777230596まで）
問題文とプログラムを貼り付けた上で仕切り直します。
プロンプト
ここからの改善を提示してください
返答です。
---（ここから）---
現在のコードは基本的な機能（クラスタリング、シミュレーション、結合）を備えていますが、スコアを伸ばすための重要な要素がいくつか欠けています。特に「今は近いが、待てばもっと近づく（あるいは遠ざかる）」という相対速度を考慮した判断が不十分です。
以下の3点の改良を加えることで、大幅なスコアアップが見込めます。
- 改良の方針
- 未来位置に基づくクラスタリング
- 現状: t=0 の初期位置だけでグループ分けしています。
- 問題: 初期位置が近くても、速度が逆向きならすぐに離れてしまいます。
- 改良: t=300∼400 程度（シミュレーション中盤）の予測位置に基づいてクラスタリングを行います。「将来同じエリアにいる原子」をグループ化することで、移動コストを削減します。
- 「最接近時刻」での結合（Local Minimum Strategy）
- 現状: 閾値以下なら即結合、終盤のみ未来予測というロジックです。
- 改良: 全期間において、「次の瞬間に距離が縮まるなら待つ、広がるなら今結合する」 という判定を入れます。これにより、すれ違いざまの最も近い瞬間に結合できるようになります。
- トーラスを考慮した重心計算の修正
- 現状: 単純な平均をとっていますが、トーラス空間（0と99999は隣接）では単純平均は不適切です（例：0と99999の平均が49999になってしまう）。
- 改良: 重心計算時に座標の正規化を行います。
- 未来位置に基づくクラスタリング
---（ここまで）---
このプログラムを提出すると、得点667806406を得ます。（私は提出していないので、この参加記を書きながら提出して確認しました。）
結合のための閾値を調整して提出すると、得点717,486,200を得ました。順位は400人中12位になりました。
プロンプト
これを初期解として、あるグループAの一番長い辺の先にある頂点C（葉）とあるグループBの一番長い辺の先にある頂点D（葉）をswapしてグループに入れた場合のコストを計算し、焼きなましで最善のグループを作ってください
簡単のため、連結するターンはCがAと連結したターンにグループBと連結する、DがBと連結したターンにグループAと連結すると考えます。
グループのどこと連結するかは一番辺の長さが短くなる頂点を選ぶようにしてください
2つの辺の長さの和がswap前より短くなっていたらスコアが改善していると考えて良いです。
このプログラムを提出すると得点741557687を得ます。（この参加記を書きながら提出しています。本番109位相当、パフォ1976の得点です。）
下図はturn0の比較です。左はこれまでのturn0の座標でグループ分け、右は新しく取り入れたturn300で分けたグループ分けです。移動を考慮する（今はt=300の座標を使用）と、初期の座標とは異なったグループ分けを行っていることがわかります。
このプログラムの結合条件の閾値を端から試して、一番良さそうなものに変えます。
double th = 35000.0 + t * 10.0;
提出をすると、得点777,230,596を得て、4位になりました。（調べたところ、ここで終わっても本番48位、パフォ2290を得ることができるようです。）
スリーセブンで縁起がいいな。これは入黄したかも…。
そう思った瞬間でした。
6.やめた解法(ビームサーチ)
ここからの改善方法で迷っていました。
プロンプト
さらなる改善で２案で迷っています。一つは、その原子を連結するターンをよりコストの小さいタイミングに変更する焼きなましを追加すること（これまでのものを１秒、今回を0.8秒行う）
もう１案は、グループが10以上あるときのマージするグループを変更する焼きなましです
案を評価してください
返答：
---（ここから）---
結論から申し上げますと、案2（結合するペア・順序の変更）の方が圧倒的にスコア改善の余地が大きいです。
案2の概要です。
- 初期解生成:
- t=300 時点の予測位置を用いて K-means クラスタリングを行い、初期グループを決定します。
- グループ割り当ての最適化（焼きなまし法）:
- 制限時間（約1.5秒）まで、以下の操作を繰り返します。
- 評価: 高速な貪欲シミュレーションを行い、総コストと結合履歴（どの結合が高コストだったか）を取得します。
- 近傍操作: コストが高かった結合において「吸収された側（葉）」の原子を選び、別のグループの原子と交換（Swap）または移動します。
- スコアが改善すれば変更を確定します。
- 結合プロセスの最適化（グループ単位ビームサーチ）:
- 焼きなましで決定したグループ割り当てに対し、各グループ独立にビームサーチを行います（残り時間を使用）。
- 状態: 各原子の位置・速度、コンポーネント構成、累積コスト。
- 遷移:
- 「何もしない（待機）」
- 「結合候補ペアAを結合」
- 「結合候補ペアBを結合」...
- これらを Local Minimum Strategy（近づいている最中は待つ）に基づいてフィルタリングしつつ分岐させます。
- これにより、単なる貪欲法では見つけられない「今は待って、より良い配置になってから結合する」手順や「結合ペアの順序入れ替え」を探索します。
---（ここまで）---
まあそうだよね、と思います。実装方法はビームサーチでした。
プログラムを提出したところ、TLEでした。（本番のときには提出をしていなかったので、この参加記を書きながら提出しました。）
本番中もどうしたらよいのかわからずにストップしました。自分のわからない解法は、どうしたらよいかも、よくわからないものです。
7.さらなる改善（得点811591192まで）
仕切り直します。
プロンプト
さらなる改善をします
一番スコアがかさんだ辺とその葉の原子を選びます。
その原子の1000ターン分の動きをシミュレーションして、いちばんスコアが低くなるグループに入れます。
そのグループの数が30より大きくなったら、29個のグループに、いちばん長い辺を持つ葉の原子をグループから切り離して入れます。0.5秒の間、焼きなましを行い、ベスト解を出してください。
返答：「以下は、指示された改善戦略（最悪辺の葉を選択→1000ターン予測して最適グループへ移動→あふれたグループから最悪辺の葉を押し出す→焼きなまし）を実装したC++コードです。」
おお、生成AIが自分の拙い指示を理解してくれている、とうれしく思いました。
提出すると得点799107753を得ます。（この文章を書きながら提出しています。）
自分は調整を入れてから提出をしています。原子の入れ替えの際、長い辺上位5個から選んでいたのですが、それを8個に変えて、得点804,461,641を得ました。この8個という数字もいくつか試した中でよかったものを選択しています。
過去のコンテストで計算の簡略化のしかたが悪くてスコアを落としていたことがあったので、ここでスコア計算方法の確認を行います。
プロンプト
焼きなましのスコア計算を、省略した版ではなくきちんと計算した場合のプログラムを書いてください
現在と比較したいです
デバッグ出力にスコアとループカウント、改善履歴を出してください
思っていた以上に本当に試行回数が少ないのですが、seed0では、初期解のスコア 4756734 が 5323182 まで上がっていることがわかります。
これを提出をすると得点808942395を得ることができます。（この参加記を書きながら提出をした結果です。）
自分は少し調整（候補数や閾値等）を入れて提出し、得点811,591,192を得ています。
手詰まり。アイデアがなくなったので、とりあえず更なる改善があるかを聞きます。
プロンプト
更なる改善があれば教えてください
返答：
---（ここから）---
改善ポイント
- 部分再シミュレーションによる高速化 (Partial Simulation)
- スワップ相手の選定ロジック強化 (Smart Swap Matching)
- 現状: グループAの「悪い原子 u」を選び、良さそうなグループBを選んだ後、Bからは「悪い原子 v」を適当に選んで交換しています。しかし、v
がグループAにとって最悪の相性かもしれません。 - 改善: グループBの候補（葉）の中で、グループAに移ったときに最も相性が良い（距離が近い）原子 v を選んで交換します。これにより、両方向でメリットのある交換になりやすくなります。
- 現状: グループAの「悪い原子 u」を選び、良さそうなグループBを選んだ後、Bからは「悪い原子 v」を適当に選んで交換しています。しかし、v
- 初期解の精度向上 (Multi-point K-Means)
---（ここまで）---
このプログラムを提出すると、得点752134164を得ました。（この文章を書きながら提出しました。自分は提出せずに、ここでストップしています。）一度に複数の事項を変更すると、何が効くのかわかりません。
8.ラスト1時間（得点856800493まで）
今あるプログラムを見直します。これまで、今結合するかどうかを1ターン先の位置が今より近づくか、離れるかで判断していました。それを10ターン先に変更します（10ターン先にしたのは数値を変えて複数試した結果です）。
t=300でグループ分けをしていたものをtの値を複数試して結果を比較し、t=350に変更します。
最後のプロンプトはこれです（以前のコンテストでも同様のことを行ったことを思い出します）
高速化をしてください
得点は856,800,493になり、順位は4位になりました。コンテスト終了まで残り3分の時点でベストスコアを更新することができました。
そして、コンテストが終了しました。
9.最終結果
結果は701人中4位、パフォーマンス3055が出ました。そして、入黄しました。コンテストが終わったときは心臓がバクバクとしてしまって、どうしようもありませんでした。
10.終わりに
ところで、今回の生成AIがあまりに良いプログラムを返してくるので、不安になって、こんなプロンプトを投げていました。
私はコンテスタントです。このgeminiで他の人のソースコードを閲覧したりしていませんか。
生成AIの使用は許可されています。
返答：
---（ここから）---
いいえ、私は他の参加者のソースコードを検索したり、閲覧したりしていません。
先ほど提供したコードは、あなたがプロンプト（入力欄）に貼り付けたコードをベースにして、一般的なアルゴリズムの知識（焼きなまし法、C++の高速化テクニック、物理シミュレーションの計算省略法など）を用いて、私がその場で改修・最適化したものです。
具体的には、以下の手順で作成しました。
- 入力コードの解析: あなたが貼り付けたコードを読み、問題のルール（トーラス構造、結合と移動のロジック）と、現在の実装のボトルネック（毎回 run_simulation で全計算している点など）を理解しました。
- 高速化の適用:
インターネット上の特定の個人の解法や、コンテスト中の他の提出物を参照することはシステム上も不可能ですし、行っていません。したがって、提示したコードはあなたの提供したコードの改良版として、安心してご自身の責任の範囲でご使用ください。
コンテスト頑張ってください！
---（ここまで）---
今回の私の結果について、生成AIを使えば誰でも出せるものなのかどうなのか、気になっていたのではないかと思います。正直なところ、優秀だなあと感じました。自分は知らなかったのですが、新しいモデルが出たばかりのようでした。同じGeminiのモデルを使った人がいれば、ぜひ話を聞きたいところです。
さて、私自身、今回のコンテストで特別なことをしたという実感はないため、解法ガチャに当たったのかなと思っています。コンテスト中に感じていたのは、各テストケースのスコアがほぼ均一だったため、seed0を改善すれば全体の底上げをできそうだということ、パラメータを変えるとスコアが大きく変動すること、未来予測を入れるとスコアが劇的に良くなることでした。
遅かれ早かれ、生成AIの使用が規制される日も来るのではないかと思っています。もしルールで禁止されれば、もちろん使用しません。そのときは、私の短期AHCでの順位は確実に下がるでしょう。
それでも今回の結果が、同じようにAHCに取り組んでいる方の励みのひとつになれたのなら、とてもうれしく思います。4年前にAHCを始めた頃の自分からは、今の Heuristic Rating なんて想像もできませんでした。また、前回のコンテストでは、自分の力不足を痛感して、もう一生、入黄なんて無理だろうと思っていたところでした。
でも、続けていると、このような日が来ることもあるのですね。
というわけで、最後にあらためて言わせてください。
やったー！入黄しました！うれしい！
お祝いの言葉をくださった皆様、本当にありがとうございました！今回の結果を励みに、これからも努力を重ねていきたいと思います。
11.おまけ：AHCラジオ
AHCラジオは、AHCの解法を学べる、とてもおすすめの公式YouTube配信です。
今回のAHC057についても、2025年12月4日午後8時からLIVE配信される予定です。初WriterのPrussianBlueさんをゲストにお迎えするので、今から楽しみにしています。皆様もぜひご覧ください。
