AHC045の日記〜ChatGPTとの200の対話で最終50位達成！〜

AHC045、対戦ありがとうごさいました!プレテスト58位、最終50位（パフォ2292）となりました。

1週間以上にわたる長期AHCの期間中、本格的にGitHub Copilot（ChatGPT-o3mini）、時にはスマホのChatGPT（無償版）と対話しながら、合計200問を超えるやりとりを行いました。そのうち、GitHub Copilotとのやりとり（プロンプト部分）について、ほぼ全てを公開して、解説します。

1. 問題概要

長期AHCの問題、理解するまでが一苦労です。問題解説をChatGPTにお願いしました。いい感じにまとめてもらっており、問題の理解が進みます。

なお、AtCoderの問題は、コンテスト開催期間中は認証がかかっていますので、一度問題をコピペして、ローカルにproblem.txtを作って保存しておき、GitHub Copilotでその問題ファイルを参照するようにすると、よいです。プログラムがある程度できたら、プログラムに参照を切り替えます。

GitHub Copilot

以下、問題概要をまとめます。

• 都市と座標情報
  N=800 の都市が存在しますが、各都市の真の座標は直接与えられず、各都市について存在可能な座標の長方形範囲 (lxᵢ, rxᵢ, lyᵢ, ryᵢ) が入力されます。実際の距離はこの真の座標に基づくユークリッド距離の整数部分（小数点以下切捨て）で計算されます。
• 占い師へのクエリ
  最大 Q 回（Q=400）のクエリを通して、占い師から補助情報を得ることが可能です。各クエリでは、サイズが 2 以上 L 以下（Lは3～15）の都市集合 C を指定し、その集合に対して MST（最小全域木）を構成する際の道路（エッジ）の組が返されます。これにより、本来把握できない都市間の真の距離情報の一部を利用できます。
• 道路建設計画とグループ分け
  与えられた入力では、M 個のグループに各グループのサイズが配列 G で指定されています（∑ G[i] = N）。目的は、各グループ内で都市同士が道路によって連結となるように、グループ内の道路（G[i]-1 本）を選択することです。また、道路の総長をできる限り短くすることが目標となります。
• まとめ
  全体として、制限されたクエリ回数を活用して隠れた真の座標情報の一部を補完しながら、各グループ内の連結性を確保しつつ総道路長を最小化する道路網の設計、という問題となります。

2. 筆者の解法の概要

以降のやりとりの理解を深めるため、最終的な筆者の解法を示します。

筆者は、重要度サンプリング（一種の粒子フィルタ、劣化版MCMC）を使って推定を行い、その推定結果を使って問題条件を満たす最小全域木（MST）を構築しました。重要度サンプリングでは、

3. 実録! ChatGPTとの議論

上記の解法に至るまで、ChatGPTとさまざまに「議論」しました。
その全過程を紹介したいと思います。なお、長くなってしまうので、プロンプトのみの公開です。ChatGPTの回答は省略しますが、だいたいの雰囲気は伝わるものと思います。

3.1. 解答方向性の確認

初期のリコメンドとしては、MST分割に集中した意見をもらいました。

1. 問題概要と解答方針案を最大3つ示せ

3.2. 推定部分に対して具体的な追求

そこで、「ベイズ推定」や「MCMC」といった、しったかワード、を並べてつっこんで聞くと、推定部分についていろいろ教えてくれます。この段階では「変分推論」を提案されました。

1. クエリから得られる情報は、L個以下の都市による完全グラフの中でMSTは何か？だと思います。この事実を使うとベイズ推定・MCMCに寄与するのでは？
2. 各都市の位置は、与えられた長方形の中で一様分布ですか？
3. 都市の位置の確率分布は、長方形の中の一様分布だと思います
4. いえ、長方形 lx, ly, rx, ryの中で、x, yの位置を示す活利分布は一様ではありませんか？
5. 切断点」や「弱い辺」はどうやってみつけるの？
6. 占いに対して、ベイズ推定かMCMCを使って、各都市の真の座標を推定することは可能ですか？
7. クエリから得られる情報は、L個以下の都市による完全グラフの中でMSTは何か？だと思います。この事実を使うとベイズ推定・MCMCに寄与するのでは？
8. 効率的な近似やサンプリング手法の工夫、について、提案してください
9. クエリは最大Q=400回、制約時間は2秒、一度のクエリーで推定される都市数L=最大15、であることを考慮して、提案してください
10. 各クエリで与えられる15都市は、クエリごとに独立はしていません。その際、どのようにして評価すべきですか？
11. N=800都市あるため、サンプル数が莫大になると思います。どうしますか？
12. ギプスサンプリングについて概要を教えてください
13. 変分推論について概要を教えてください
14. どちらがよいでしょうか？
15. Q=400回のクエリにおいて、初期は大域的な手法、後期は局所的な手法を組み合わせるのはどうですか？
16. 大域的手法について、疑似コードでアルゴリズムの概要を教えてください
17. クエリはL個以内の任意の都市を選択可能です。その要素を考慮してください
18. そうではなく、クエリする都市をどこにするかも含めて、最適な手法を提案してください

3.3. 推定部分とMST構築部分の関連部分の追求

推定部分の方向性が見えたので、MST構築部分との関連を確認しました。

1. 今回の問題では、完全なMSTを求めるものではなく、Gi個ずつのグループに任意に都市集合を分割したうえで、それぞれのMSTを求めて、全体を最小化するものです。この問題特性を取り入れて、改善すべきポイントはありますか？
2. グループを考慮しないまま推定精度をあげていって、最後の解答でグループを考慮した最適値を出す、という方法もあると思います。比較考察してください
3. そうすると、初期の大域的手法はグループ分割を考慮せずに、中期でグループ分割し、後期で分割グループごとの局所手法を適用しつつグループ見直しを行う、という流れでどうですか？

3.4. 実装の確認

変分推論とMST構築に関する実装を、確認しました。途中で、バグ特定にも役立ってもらいました。

1. KL_divergence、compute_gradientsもよろしく
2. ELBO_funcも例示ください
3. KL_divergenceも教えて
4. generate_candidate_queriesにおいて、クエリーをランダムではなく、推定値をもとにより効果的に求める方法はありますか？
5. 初期の推定結果を基に、各都市をグループ分割するための、アルゴリズムを教えてください
6. Giは順列変換可能である特性を考慮してください
7. グループi, jに対して、2都市の入れ替えだけでなく、Gi, Gjの入れ替えも考慮すべきでは
8. 各都市の位置が完全に決定しているときに、グループ分割とMSTを時間内に厳密に求めるアルゴリズムはありますか？
9. ヒューリスティック手法を提案してください
10. 全体の解法として（中略）としましたが、Wが500以上と、分割数が大きいので、後期段階は省略してもよいですか？
11. 道路は互いに交差しても問題ありませんか？
12. 167-185行目を実装してください。distsが小さい順に操作していき、2つとも同じグループならグループ統合を、片方だけグループに属しているならグループに追加を試しつつ、num_group_limit と同じサイズのgroupになるようにする
13. エラーをなおしたい
14. 510-514行目のエラーをなおしたい
15. （エラーメッセージをそのまま貼り付け）
16. 以下のestimate_information_gainの引数のmu, sigmaは何？（Copilotの回答を貼り付け）
17. ELBO_funcの例を示せ
18. prior_distributionとは？
19. 以下の実装において、prior_distributionとは何か？（Copilotの回答を貼り付け）
20. 具体的な実装を示せ
21. 定数なの？
22. predictied_mst と obserbed_mst が同一になってしまう
23. generate_candidate_queriesにおいて、candidate_citiesに近い候補を選択するのはどうですか？
24. この戦略は有効ですか？
25. generate_candidate_queriesについて、candidate_citiesごとに近辺の都市を選定する、という方法はどうですか？
26. elbo_func の実装例を示せ
27. ターゲットはわからないのでは？
28. もう一度、大域的手法について、疑似コードでアルゴリズムの概要を教えてください

3.5. 推定の方針転換、粒子フィルタへ

ChatGPTの実装案が問題にあっていないため、方針転換を議論しました。

1. 今回は、観測できる情報がMSTだけなので、微小な変化では観測結果が変化しないような、フラットな特徴量であるように思います。そのため、この手法は使えないのでは？
2. 変分法はあきらめて、期待分布をもとに1000個程度のサンプリングをして観測結果と比較すべきでは？
3. 疑似コードが途中で切れています
4. それではなく、欲しいのはモンテカルロサンプリングのコードです
5. 疑似コードでよいので、モンテカルロについて、best_queryの導出、クエリー実行、結果をもとにした予測改善の全体を示してください
6. [3]は ガウス分布のmuを使えば良いので、無駄では？
7. わかるけど、best_queryを求めてから、その不確実性を求める方が効率的では
8. [5]で期待値だけ求めるのではなく、分布全体をもとに、クエリー結果を使って、各都市のmu, sigmaを更新できないか？
9. 各都市の事前分布は長方形内で一様であるとともに、途中結果によっては、確率としての峰が複数できるなど、ガウス分布では近似しにくいのでは
10. 粒子フィルタだと、L=15の場合に各都市の粒子を複数持つと計算量が大きくなりすぎるのでは
11. L=15だと、2粒子でも、2^15になりますよね。無理では
12. サンプリングベースの手法で、各都市の分布を表現する際、ガウス仮定に過度に依存しない方法を採用する、について、もう少し教えて
13. N=800の場合、Kはいくつにするとよいですか？
14. K=2〜5の場合、長方形の中でどのようにして初期粒子位置とその確率を決めますか？乱数選択するには粗すぎるように思います
15. 長方形はほぼ正方形なので、K=4がよいのでは
16. 初期面積に応じて、K=2^2〜10^2の分割により粒子を作り、その中からモンテカルロサンプリングで評価し、事後確率を求めつつ、各長方形内で選択されなかった粒子を含めてて連続性を活かして更新する、という方法はどうでしょうか？
17. 都市ごとの平均や分散ではなく、粒子ごとの確率を事後計算するのでは
18. 分布を元にモンテカルロで各都市の位置をサンプリングする方法を行いたいです。分布の表現方法（データ構造）、試行結果による分布の更新方法、最新の分布にもとづく乱択方法を教えてください
19. 粒子の位置は固定せずに、毎回のサンプリングで新規に選択したいです。方法を提案してください。
20. ノンパラメトリックにする方法はありますか？
21. 粒子集合は毎回変動させる前提で、次回以降のサンプリングをする方法はありますか？
22. ガウス過程で分布を求めていく方法はどうですか？
23. 一度に値更新できる都市数は最大L=15なので、なんとかなりませんか？
24. やはり、リサンプリングの方法がわからないです
25. 2次元にしてください
26. CDFは2次元の中でどのような順番に計算しますか？
27. リサンプリングで、粒子の位置を変えたいです
28. まずは元の粒子の新しい重みでサンプリングして、そのあとに接道を加える、ということでしょうか？
29. なるほど。初回は一様分布の仮定で同じ重みでサンプリングしつつ、L=15に対して、合計1000個程度のサンプルを得る、結果のMSTを観測MSTと比較評価して重みを更新、更新した重みで再度、L=15に対してサンプリング、結果に接道を加え繰り返す、でよいですか？
30. 摂動させる方向や距離は完全ランダムでしょうか？
31. この一連の方法にはな何か名前がついていますか？
32. 各長方形の中の粒子は、1000個のサンプルの中での出現率がまちまちです。これをどのように粒子の存在確率にフィードバックしますか？
33. なるほど。単純に平均尤度に対して、出現確率で重みづけする、ということですね

3.6. 精度向上への道

実装は一通りできたのですが、あまり精度が上がらないため、いろいろ試行錯誤をしました。（途中）

1. あまり精度が上がらないのですが、211行目の尤度計算について改善案はありますか？
2. あまり変わらないか、悪化しました
3. MSTの構造（たとえば、共通エッジ数など）と総長差を組み合わせた複合指標　を試してみたい
4. 少し良くなったけど、まだすっきりしない
5. 真の都市位置と想定位置とのMSEが、L=15なら初期解から20%くらいまで下がるが、L=3なら初期解から80%くらいまでしか下がらない。Lが小さい時の手法を変えたいが、どのようなものが考えられるか？
6. 後半の分割後にクエリバジェットを残しておいて、サイズ3〜15の分割について解を求める作戦はどうてすか？

3.7. MST構築部分を深く追求(1)

MST構築部分も確認し改善しました。実は、この時点でChatGPTからは全体のMSTを構築してからカットすることを提案されました。しかしながら、実装が見えないため却下して、制約内で順次作っていく方式を指示してしまいました。上位陣は全体からカットしていたようでしたので、もう少しつっこんで聞くべきでした。

1. AgentCluster::init にてMST被覆をしています。このアルゴリズムを評価して、よりよいアルゴリズムを提案してください
2. ハイブリッド手法について、実装変更提案してください
3. 全体のMSTから辺をカットして得られるクラスタは、クラスタ制限サイズとかなり異なるため、調整困難では？
4. ハイブリッド・フェーズ方式って、まさに今やっているやつでは？
5. グループ分割はかなりうまくできた

3.8. 推定が困難なL=3を追求

いろいろ特徴量を追加して尤度推定を改善しました。

1. 前半で、Lが小さい時の戦略をどうすべきか？
2. 4は無理。Lが上限であるため
3. 重複クエリの活用や、オーバーラッピング戦略について、もう少し詳しく
4. 具体的にどのようにクエリを統合するの？
5. クエリから得られる特徴量として使っていないものはある？
6. エッジ長の分散を特徴量として加える実装を示せ
7. クエリから得られる特徴量として、L=3でも効果あるものは？
8. 各都市の位置はその時点の推測であり、実際の位置は不明です。確実に判明するのは部分MSTの形状のみで、距離に関する情報は推測をもとにしたものです。この前提で考えた時、L=3での有望な特徴量はなんですか？
9. すべて絶対距離に起因する指標だと思います
10. 再度整理すると、位置は推測でしかわかりません。エッジ長比も内角もすべて推測にもとづく指標ですので、適切ではないのでは？
11. 現在、不確実性をもとに候補都市を決めて、その都市の近距離順のL個の都市を選択するとしています。この特性を使うと、最初の候補都市のMST次数が有力な特徴量と思いますが、どうですか？
12. compute_likelihoodの実装を提案してみてください。
13. まず degree_factor =1.0固定にしましたが、元の実装と比較してやや悪化しました。なぜでしょうか？
14. いえ、degree_factor導入前との比較です
15. 現在、generate_candidate_queriesでN=700回の操作をしています。generate_candidate_queriesはQ=400回以上の呼び出しをcandidate_cities.len()=50回行っています。これを高速化する提案をしてください
16. muは固定ではなく、毎回L個の都市が変更されます。それを考慮してください。

3.9. MST構築部分を深く追求(2)

MST構築をもっと効率よくできないか、試行錯誤しました。なお、最後の方で、MSTの形状を見るために、ミニビジュアライザを即興で作ってもらっています。

1. 現在のAgentCluster.init()の方法だと、Mが比較的小さい時<100の際に、長大なエッジができてしまいます。なぜこのようなことになるのか、分析してください
2. unused_pairsではなく，unused_edgesを管理し、毎ターン、短距離の未接続辺から接続可能性をテストしていく、という手法は有効ですか？
3. 大規模クラスタは長距離辺ができにくい、と考えられます。先に小規模クラスタを決めてしまう、という手法は有効ですか？
4. もっとシンプルに、中心からの距離に反比例するようにエッジに重みを加えるのはどうですか？
5. 逆です。中心に近い方が長く評価されます。そうすると周辺部は比較的に先にグループ化がされるため、長いエッジが残りにくいように思います
6. AgentCluster.init()にて、強連結成分分解後にトポロジカルソートしているのですが、トポロジカルソートに失敗します。なぜ
7. AgentPredPos.estimate_information_gain を改善したい
8. queryのサイズは固定なので、平均などはとらなくて大丈夫
9. トポロジーによってはcount_cosは変動するのでは？
10. クエリに含まれる各都市間の距離の分散に反比例する指標はいかがでしょうか？距離が揃っているクエリーが優先され、誤差を加味して多様な結果が得られるため、得られる情報量が大きいと思います
11. 本当ですか？自信ありますか？
12. クエリ先頭の都市と、他の都市との距離を比較して、2番目に小さい距離に反比例する指標はどうでしょうか？最終的にクラスタになった場合に、孤立点や2点のみのクラスタは優先させない戦略です
13. 803行目からi行を座標として図示せよ。python matplotlibインタラクティブ機能を使って、スライダで入力ファイルの変更と、iを変更できる
14. さらにMSTとなる辺を線で結べ
15. MSTが描かれない

3.10. クエリ選択の改善

クエリを効率的に選択できるように、情報利得の試算を改善しました。後半は再度、尤度の改善を行っています

1. estimate_information_gain() でバグがあるのにスコアはよくなります。なぜでしょうか？
2. バグを修正するとスコアが下がるのですが、どう修正するとよいですか？
3. estimate_information_gain()で、他に有効なパラメータはありますか？
4. estimate_information_gain()で、今実装されているパラメータを効果予測含めて解説し、他に有効なパラメータがあるか教えて
5. 既存の実装と新しい提案をあわせて、有望な順にしてください
6. ちょっと変えました。どうでしょうか？
7. このプログラムでパーティクルフィルタと呼んでいるものは、ギブスサンプリングでしょうか？
8. パーティクルフィルタと呼んでもよいですか？
9. compute_likelihoodで、今実現しているパラメータを効果予測含めて解説し、他に有効なパラメータも提案して、有効な順に並べてください
10. エッジ角度の一貫性因子　を実装してみました。ちゃんと実装できていますでしょうか？

3.11. MST構築部分を深く追求(3)

MST構築後に最適化を実装しました。

1. 頂点数N=800、クラスタ数M=1〜400、各クラスタに所属できる頂点数 Giはあらかじめ与えられており、ΣGi = N、頂点には2次元平面での位置が与えられている。すべての頂点間は接続可能である、この時にM個のMSTを構成して、MSTの辺の長さの合計を最小化せよ
2. 局所最適化やメタヒューリスティクスで改善するアプローチ　を教えて
3. 今回の問題への適用方法を教えて
4. 局所探索やSAなどのメタヒューリスティックを用いて、クラスタの再編成やエッジの選択を改善しながら、最終的に全体の MST 長の合計が最小となる解を目指します。について詳しく
5. もともと貪欲解において、Giは正確に守るようにしています。そのため、この近傍だとどの頂点も移動できないのでは？
6. 互いに「オーバーラップ」している2つ以上のクラスタを見つけて、破壊・再構築をする、という近傍はどうでしょうか？最初と同じ方法で貪欲に求めると、全く同じ構成に収束してしまうような気もします
7. クラスタ同士が「オーバーラップ」しているかどうかを判定するアルゴリズムを教えてください
8. 制約付きK-meansって、どうやってやるのですか
9. 最大辺を持つクラスタを特定して、オーバーラップするクラスタをAABBで特定し、すべて破壊する。最初のクラスタの最小辺からプリム法でクラスタを完成させ、そのあと残りを再構成する。という近傍はどうでしょうか？
10. 元の貪欲はクラスカル法だったのと、プリム法で最大辺をもっていたクラスタを最初に作るため、元の構成に戻る危険はありません
11. プリム法で最大辺だったクラスタを構成しなおすため、最大辺が再びあらわれる可能性はありません
12. 完全にゼロですよ
13. construct_groupsを評価して、良い点・悪い点を教えてください
14. 離れたノードを同じグループに入れることを防止するため、BoundedPartitionに「force_limit」を設けて、capacity_limitはそれ以下にし、完成したら順次force_limitを緩和していく方法を考えています。どう思いますか？
15. BoundedPartition.is_valid()において、accにプラスが出た場合、capacityの残り分の位置のnum_partitionにプラスをするのはどうですか？
16. is_valid を修正してみましたが、どうでしょうか？
17. バグってたけど、ちゃんと動いた入力条件ても、改善しませんでした。長距離エッジは残ってしまいます

3.12. 高速化

重そうなところの改善策をいろいろ確認しました。

1. MSTFeaturesのupdateのself.mean_cosの計算、間違っていませんか？
2. estimate_information_gainの方を見ていませんか？こちらら正しいです
3. MSTFeatures::updateのmean_cos計算では，u2vには距離情報は膨れませんませんね
4. となると問題はなんでしょうか？
5. AgentCluster.optimize で制限時間を40ms超過する時があります。途中タイマー脱出を設けていますが、タイマー脱出が無くて一番時間がかかっているところはどこ？
6. そこはタイマー脱出いれていますよね？確認してください
7. 次の候補はどこ？
8. いえ、，次にタイマー脱出が無くて時間がかかっているところです
9. そこの計算量を改善するには？
10. AHC_PARAMS_LIKELIHOOD_P4は、ハイパーパラメータ最適化をしても0.0（使わない）となります。他の特徴量候補はありますか？
11. 優先度順に教えて
12. コンパクトネスは、generate_candidate_queriesで保証しているよね
13. generate_candidate_queriesを高速にするには？
14. select_nth_unstable_by_keyを使って書き換えてみて
15. 遅くなった
16. BoundedPartition.is_valid() をFenwikTreeで表現すると速くなる？
17. 実装案を示してみて
18. （エラーメッセージ）
19. BoundedPartition 内に size フィールドを追加　でよろ
20. 以下、add_element, merge_partitionsなども同様に更新　の実装をよろ
21. （エラーメッセージ）

3.13. 御礼

コンテスト終了したので、御礼を申し上げました。（大事）

1. すべて終了しました。ありがとう