← ブログ一覧に戻る

AtCoder Heuristic Contest 045

#AHC #AtCoder

はじめに

AtCoder Heuristic Contest 045 に参加しました。今回は Gemini 2.5 Pro を使って一切自分でコードを書かずに挑戦するという試みをしました。

問題概要

AHC 045 は都市をグループ分けし、各グループの最小全域木（MST）を構築する問題でした。ポイントは：

  1. n個の都市があり、それらをm個のグループに分ける
  2. 各グループの都市間の距離を最小化する必要がある
  3. 各グループ内で最小全域木を構築する
  4. クエリを使って都市間の接続情報を一部取得できる

アプローチ

Gemini 2.5 Pro を使って開発したアルゴリズムの主な特徴は以下の通りです：

1. クエリ戦略

コードでは都市の面積に基づく確率的なクエリ戦略を採用しています：

letquery_area_probability = config.query_area_probability;

大きな面積を持つ都市を中心にクエリを行い、その周辺の都市との接続情報を取得することで効率的に情報を集めます。

2. 初期解生成

Farthest Point Sampling (FPS) と呼ばれる手法を使って初期シードを選定：

let seed_indices = select_seeds_fps(m, &cities, &mut rng);

これにより空間的に均等に分布した初期グループを作成しています。

3. 焼きなまし法による最適化

コードの中心は焼きなまし法による最適化です：

let mut T = config.sa_t_start_factor;
let T_end = config.sa_t_end_factor;
let alpha = config.sa_alpha;

3種類の近傍操作を組み合わせています：

  • ソリューションの一部を摂動させる（perturb）
  • 都市の移動（shift）
  • 都市の交換（swap）

4. 効率的な評価関数

グループのコスト計算を効率化するための統計情報を使用：

struct GroupStats {
    count: usize,
    sum_x: i64,
    sum_y: i64,
    sum_sq: i64,
}

これにより全体の再計算なしでコスト差分を高速に評価できます。

5. 最小全域木の構築

最終的な各グループに対して、Kruskal のアルゴリズムを使用して最小全域木を構築：

let mut dsu = Dsu::new(n);

クエリで取得した接続情報を優先的に使用しています。

Gemini 2.5 Pro との対話

Gemini 2.5 Pro とのやり取りはこんな感じでした。

  1. 問題を要約してもらう
  2. 適当に考察し、以下の方針でコードを書いて貰う
    • N個の都市を $K$ 個のランダムな頂点に分けて、クエリを投げる
    • それである程度位置推定した後、FPSにてコアグループを選び、貪欲法で MST を構築
    • 焼き鈍しで最適化
  3. 出来上がったソースコードと問題文を投げて、高速化の依頼など

結果と考察

全くコードを書かなかったとはいえ、あまり良い結果ではありませんでした。 上位陣の解法を見たら、割とみんな位置推定をしており、最初の方針を突き詰めた方が良かったのかもしれません。 考察と言っても今回は何も分からず、上位陣の少し追ってみたんですが、 Gemini でうまく再現できるような解法がありませんでした…。

今後の改善点

  • そもそも知識が足りなかった MCMC など知らなかった。
  • Gemini が勝手にサボることがあるので、もう少し細かく指示を出す必要がある。
  • クエリの戦略をもう少し考える必要がある。特に、クエリの数を減らすための工夫が必要。

まとめ

この記事も大雑把に Claude に書いて貰いました。 いや、かなり書き換えたから、そのままではないんですが…。

1行もコード書かずに、 AHC 高レートになりたい！と思って居るんですが、まだまだ道は長そうです。

← ブログ一覧に戻る