AHC (AtCoder Heuristic Contest) 攻略法をレッドコーダーにインタビュー

はじめに

2025/12/13に開催されたAtCoder Conference 2025で、ゲストスピーカーとして発表を行いました。お越しくださった皆様ありがとうございます！ speakerdeck.com 発表後半で、AHCレッドコーダーにインタビューした内容を紹介したのですが、当日発表できなかった部分でも多くの素晴らしい知見があったので、公開します。

回答にご協力いただいた方々

本当にありがとうございます！（ちなみに、日本橋ハーフマラソンの懇親会で近くのテーブルにいた皆さまにお願いしました。）

saharanさん

• AHCレーティング 3360 世界1位
• 現在世界最強の方です。AWTF 2025 世界4位。AHC優勝4回。ハル研プロコン等で活躍されてましたが、最近は強さが極まっています。競プロ以外のCGシミュレーション分野の趣味プログラミングでも有名な方です。
• AtCoder, X(twitter), おいもログ | shr's tech diary

montplusaさん

• AHCレーティング 3168 世界8位
• AWTF 2025 世界5位。AHC048 優勝。大学生で数少ないAHC世界ランカーで今後もさらなる活躍が期待されます。
• AtCoder, X(twitter), 記事一覧 - MON.T+α Programming Room

tomerunさん

• AHCレーティング 2839 世界27位
• TopCoder Open Marathonの決勝に5回出場。ベテランのヒューリスティック第一人者です。AHC以前から「日本橋ハーフマラソン」も開催しており、コミュニティへの貢献も素晴らしい方です。
• AtCoder, X(twitter), TopCoderの学習のお時間

simanさん

• AHCレーティング 2810 世界33位
• TopCoder Open Marathonの決勝に2回出場、また、ゲームAIコンテストでも長年活躍しており、CodinGameでも優勝経験があります。
• AtCoder, X(twitter), simanのブログ, scorerun

質問集

質問1.
AHCで貪欲法が重要とされていますが、攻略の定型化は難しいと考えています。貪欲法を使用する際に、意識している点や工夫している点はありますか？

saharan
「どの要素を簡略化するか」というのが難しく、いつも注意して考えるようにしていますが、しばしば失敗します。また、いきなり賢い貪欲法を書こうとせず、まずはすごく単純なものを書いてみて、ビジュアライザで挙動を観察しながら次はどこに手を付けるとよさそうかというのを考えるようにしています。あとは、「焼けそう！」と思ってももう少し我慢して貪欲を考える、というのを意識するようにしています。

montplusa
（ここでは、少なくとも何らかの評価関数が後ろで見え隠れしているタイプの貪欲法について書いています） 最適化問題を考えたとき、最小化・最大化したい指標に対してまさしく"貪欲に"採用するようなアルゴリズムが一番最初に思いつきますが、その後に将来的にツケが回ってくるような要素があればその分評価を減衰させて評価するというような構造にできないか考えます。 例として、「魔法使いがボスとの戦闘を終えるのにかかるターン数を最小化する」みたいな問題を考えると、1ターンのダメージを最大化したくなりますが、MP消費が激しい魔法では後半でMPが枯渇して失速してしまうので、制約によってはMPの効率を意識したほうがよかったりします。

tomerun
貪欲というと目先の利益だけで動いていくという印象がありますが、そうならないよう、あくまで理想的な状態を考えてそれに近付いていけるような方法を考えます。

siman
自分は貪欲法が得意とは言えませんが、takapt さんが書かれていた「確実に前進」という指針は今でも強く意識しています。

「Topcoderマラソンマッチの探索問題で重要なこと」 https://qiita.com/takapt0226/items/b2f6d1d77a034b529e21

普段はまず、その盤面から打てる合法手をすべてピックアップし、その中から「この手を打つと確実にスコアが上がる（もしくは悪化しない）」ものを探す、という考え方でやっています。ただ、これはやってみるとかなり難しいです。

貪欲法は本質的に「常に良い状態を選び続ける」手法なので「一時的には盤面が弱く見えるけれど、最終的にはそのほうが良くなる手」の評価がとても難しくなります。そういうケースでは、1 手進めたうえで、その評価関数の中でさらに「N 手ぶん簡易シミュレーションしてみる」といった工夫を入れることもあります。ただし、このやり方だと 1 手あたりの評価コストが重くなってしまうので、「もっと軽量な近似評価でうまく代用できないか？」といつも悩んでいます。

自分の中で、貪欲法における基本的な評価関数のイメージは 問題のスコア + 良い特徴量 - 悪い特徴量 という形です。そして、この「良い特徴量」と「悪い特徴量」にどれだけ気づけるかが、貪欲の強さを大きく左右すると思っています。とはいえ、何が良くて何が悪いのかを判断するのは簡単ではなく、結局はいつもビジュアライザとにらめっこしながら試行錯誤しています。

盤面状態に関するあらゆる情報を可視化しておき、「どのような状態になっていれば良いのか」を考察しやすい環境を作ることが大事だと感じています。AHC は標準のビジュアライザがよくできているので、それをそのまま使うだけでも十分に考察はできますが、生成 AI がある現在では、独自のビジュアライザを用意しつつ、問題のコアな部分を理解・抽出するための可視化の重要度が、以前にも増して高くなっているのではないかと感じています。

質問2.
焼きなまし法・ビームサーチなどの定番アルゴリズムで、他の人とは違った工夫をしている点はありますか？

saharan
ビームサーチでは、差分更新ビームサーチ (Euler tour beam search) を使うことで、今考えている問題（保持すべき状態が大きい）にビームサーチが適用できるようにならないかというのを必ず考えるようにしています。焼きなまし法では、これといった一般的な工夫は特にしていません。問題ごとのスコアの差分計算や近傍の質が全ての鍵を握っている印象です。

montplusa
ビームサーチでは、高度化する前は必ず評価値計算ののちに小さめの乱数成分を乗せるようにしています。というのも、次候補の評価値に大きな団子地帯があると、それにわずかに及ばなかった実はよい候補が淘汰されてしまい、似たような団子地帯の候補ばかりが残るという現象が起きます。実装初期はこの現象によりビームサーチの効果があまり実感できないことが多く、誤って「方針に見込みがない」と方針を捨ててしまわないようにしています。実装を詰めていくといわゆる重複盤面の除去や評価関数の改善などにより、段階的にタイブレーク+α程度に影響力を下げていっている記憶があります。

tomerun
ライブラリ化をしない（極限まで最適化をしようとすると結局全体に手を入れることになるので）（ほとんど整備をサボっていることの言い訳です…）

siman
焼きなまし法はそんなに得意ではないので他の人と異なる工夫はあまり無いかもしれません。 近傍はなるべく小さく、差分計算が可能なものを考える（イテレーションの回数を増やすため）

ビームサーチはとにかく「評価関数」と「多様性」が大事だと思っていて、重複排除のためのハッシュ関数をいい感じに設計したりとかは頑張っているかもしれません。 「評価関数」は結局、貪欲の強さみたいなところがあるので Q1の話と近いところがありますが、とにかくビジュアライザを見ながら「良い状態」とはみたいなことをずっと考えています。一応木上のビームサーチとかは手元に持っていますがここだけで差がつくみたいなことはあまり無い気がします。

質問3.
AHCで、技術的に未開拓だと感じる領域や、現状の手法では攻略しきれていない問題タイプはありますか？

saharan
参加者のレベルがとても高いので、コンテストで出された問題は概ね制約の範囲内では攻略されていると感じます。技術的には、SIMD にとどまらずマルチコアを扱うような問題や、GPU が利用可能な環境での問題が未開拓な領域だと感じています。あとは、実業務でありがちな、入出力や問題の制約が最初からは完全に決まっておらず、様々な要素や要求を考慮して最適化問題に落とし込んでいくパートなどがありますが、これはコンテストとして出題するのは非常に難しそうです。

montplusa
（質問の意図を間違えていたらすみません） AHCは競技性・楽しさの観点から極端に大きなインスタンスの問題は出ない気がしています（アルゴではよくある10⁶サイズなど）。インスタンスが大きくなると焼きなまし相対的に少し使いにくそうだなあという印象があり、計算資源が圧倒的に足りない中での最適化みたいなところはあまり知見が集まっていない気がします。（そもそも貪欲法しかなくなってしまうのかもしれませんが）

（余談ですが、以前ABCにヒューリスティックコンテストで使っている自前の入出力テンプレートで挑んだら入力長が想定より長くREになったことがあります。完全に意識の外だったので原因特定に時間をかけつつ2ペナしました。それくらいAHCのインスタンスは小さめです）

tomerun

• 多目的最適化：単にスコア関数が複数の要素を含むのではなく、それら複数の要素間の相対的な重要度に対応する複数の出力を提案するような形式
• 対戦相手が存在するようなゲーム

siman
どうしても時間制約が 2-3secになるので、長時間計算が必要となりそうな大規模な問題はあまり開拓されていないのかなと思っています。 短時間だとどうしても「焼きなまし」「ビームサーチ(貪欲)」が強くなる印象なので、もっと時間制約を緩めることで新たな手法が有効になってくるのかなと思っています。（例えば機械学習とか）

質問4.
調整・検証のために使っている環境・ツールは何がありますか？ （例：可視化／ログ／テスト／ハイパーパラメータ調整 など）

saharan
ビジュアライザ： 自作の汎用ビジュアライザを利用しています。ソースコード中に描画命令（この色でここに円を描け、など）を埋め込む形式で、結果の可視化のみならず焼きなましの過程やデバッグ作業にも役立っています。

テスト： テスト環境も自作のものを利用しています。相対スコアの表示、テストケースの特性に合わせた結果の絞り込みやグラフ表示、複数提出の詳細な比較などが特に重要な機能です。

プロファイラ： プログラムは WSL 上で開発しているのですが、プロファイラだけは Visual Studio のものを使っています。ボトルネックを絞り込むのに重宝しています。これのために、Windows 上でもコンパイルできるようなコードにしてあります。

ハイパーパラメータ調整： Optuna を使うことがあります。が、多くの場合手動による調整で済ませます。これは、「良い」パラメータを設計できた場合、スコアはそれらのパラメータに対して単峰な振る舞いをすることがほとんどで、高度なアルゴリズムを使ってパラメータを探索するよりも、座標降下法などの単純な方法で一つずつチューニングしていった方が効率が良いためです。とはいえ、設定すれば寝ている間にパラメータを見つけてくれるのは嬉しいので、終盤の立ち回りに合わせて臨機応変に戦略を考えるようにしています。

ログ・デバッグ： いろんな場所に assert を仕込みまくっています。このとき、条件が破られた場合、単に失敗したと表示するだけでなく、どの式がどの値を取ったかをログに出すようにしています。

montplusa
普段はpahcer(terry_u16さん、githubにあり)を利用しています。より詳細な時間計測・比較をしたい場合はローカルジャッジを自作して1000ケースほど回し、ahc詳細順位表(wataさん、終了した長期コンテストの解説にあり)をローカルで使用しています。

tomerun
https://topcoder-tomerun.hatenablog.jp/entry/2024/04/06/201915 これです

siman
可視化: 生成AIに作ってもらいます ログ: 各テストケースのログは自前で用意しています(スコア、各種パラメーターが TSV形式で出力される） テスト: 自前の並列テストがあります。マルチプロセスで動作するので、他のテストの影響を受けにくい構成になっていると思います。 パラメーター調整: optunaで調整はするときもありますが、上位争いしている時にしかほぼ使わないです。（なので最近使った記憶が。。。）

質問5.
AIを使用していますか？使っている場合、どのような用途で活用していますか？

saharan
GitHub Copilot による補完を多用しています。また、簡単ではあるが書くのが面倒なアルゴリズムを素早く書かせたり、SIMD を利用した高速化のために ChatGPT や Claude を利用しています。たまにアイデアを出させることがありますが、もっぱら長期では役に立ちません。

montplusa
かなり利用しています。 自分で問題から最適化したい部分問題を切り出し、部分問題を解く関数を書いてもらっています。AIが書く最適化は、「それらしいふんわりした解」を出力する印象があり、一番核となる最適化部分は自分が実装することになりがちです。 ビジュアライザや手動で何かを試せるようなツールを頼んだり、ローカルジャッジを代わりに作成してもらったりということも最近は結構あります。

tomerun
デバッグの効率化

siman
コンテスト外であれば「上位入賞者のコード解説」とかで使用しています。

コンテスト中であれば「長期」はスコア解析ツールの作成や、独自ビジュアライザの作成。方針の一部で必要な関数の実装の肩代わり。戦略の壁打ち役等々、生成AIとチームを組んでいる感覚でタスクを依頼しています。 ジャッジコードを読ませることで、問題文に対してより細かい質問とかを答えられるようになるので問題理解の役にもたったりします。

質問6.
コンテスト終了後は、どのように復習していますか？

saharan
流れてきた解法を見たり、上位の人のコードを読んで方針を理解する、などをしています。特に「それは思い付かなかった」という重要な考察が流れてきた場合は、

• なぜ思いつかなかったのか
• どういう思考過程を経ればその方針に辿り着けたか
• 賢い解法だが、これは思い付けなくても仕方ないものなのか

などを分析します。

montplusa
コンテスト後にTwitterで大量の情報が飛び交うので、その時にしっかりと他の解法を見ています。近い点数の人が実は違う解法だったり、あきらめた解法ができている人がいたりするので学びは大きいと感じています。

tomerun
復習は特にしていません…（しなくて良いという意味ではないです） 復習よりかは、開催されているコンテストに出たいですからね

siman
基本的には上位入賞者の解法を見ながら復習しています。昨今は生成AIのお陰でコードを読んでもらって細かい部分の解説とかも出来るようになっているので便利です。 復習する場合は短期コンの問題をオススメします。長期コンに比べると問題もシンプルで解法も比較的シンプルになりやすいので、そこまで時間をかけずに上位のスコアを獲得することが出来ると思います。

質問7.
アルゴリズム以外で、AHC攻略に役立つと感じていることは何ですか？ （例：問題解決の進め方／思考プロセス／参加環境／体調管理 など）

saharan
ビジュアライザをよく観察する、難しいことをしようとしない、試行と改善のサイクルを短くするよう心掛ける、長い時間をかけて「最強の方針」を一度に組み立てようとしない、風呂で考える、常に 1 位を倒すことを考える、などが重要であると感じています。

montplusa
コンテスト中に気持ちを切り替える瞬間が多いと、アイデアが来やすい気がします。学業・仕事に打ち込むとか、小さなことでいえば風呂・トイレに行くなどでもかなりアイデアが来やすいです。

tomerun
重そうな実装を始める気合 情報の可視化 常に頭の中に問題のことを置いておくという点での集中力

siman
メタ戦略的な部分はありますが「逆算力」は大事だと思っていて「今1位の点数がこれぐらいか」→「つまりこの点数を取るには 1ターンにこれぐらいスコアを取る必要があって or 1ケースあたりのスコアはこれぐらいになっているはずで」→「それを達成するためには◯◯が必要で〜」みたいな感じで、上位のスコアから戦略を逆算することで割と上位者のやっていることみたいなのがわかったりすることがあります。これが嫌で上位者がたまに低いスコアをサブミットして下位の方で待機する戦略を取ることがあります。（一般的には潜伏とか呼ばれていたりします） 実際、仮にスコアボードが順位だけでスコア表示がない場合は最終的な全体スコアも低くなると思っています。（コンテスト的に全然面白くなさそうですが）

参加環境はそうですね、10日間のコンテストで 240hあると思いますが 4-50時間ぐらいの作業時間が取れる環境は上位で戦うには必要な感じがします。 体調は大事ですね、いいアイデアが思い浮かんだときについつい夜ふかししてしまうこともありますが、基本的には早寝早起きのリズムを大事にしたいです。

質問8.
AHCの4時間コンテストで意識している時間配分・進め方はどんなものですか？ また、アイディアが多すぎる場合の優先順位のつけ方・戦略があれば教えてください。

saharan
最初 1 時間くらいは貪欲による方針をじっくり考えて、2 時間時点で結果を見てその後の方針を決め、残り 2 時間で焼きなまし・ビームサーチ・貪欲を詰める、というのが理想のパターンですが、なかなか実現できていません。アイデアが多すぎるときは、あまりに自明なもの、実装に時間がかかるものを捨てて、ある程度の非自明さと実装のしやすさのトレードオフを考えて実装する方針を選択します。

montplusa
4時間でできる範囲を見積もって、それ以上に手を伸ばさないようにしています。1位を狙うのであればちょっと弱気すぎるかもしれませんが、最近の4時間コンテストは4時間では詰め切れない複雑さの問題が出てきがちなので、ある程度の割り切りが重要な気がします。 最後の1時間はチューニングに使いたいので、メイン方針自体は3時間時点で完成していたいです。

tomerun
短期コンテストだと、とりあえずの貪欲を書いて様子を見ようというのをついやってしまいますが、局所最適に陥って本質的な強い戦略に行きづらくなるように感じており、やめた方が良さそうだと最近思っています。前半2時間くらいは実験と考察に振るくらいで良いかもです。 複数のアイディアの中では、実装量と影響度のコスパが大きそうなものからやります。

siman
4時間コンテストは「問題の誤読」が一番怖いので、最初の 30分は問題理解の時間にしています。 自分の経験上早めに解き始めても終盤の数十分はパラメーター調整を行っていることが多いので、それなら前半の数十分を問題理解の時間にしようという考えです。 ここ最近は生成AIのお陰で「とりあえず思いついたアイデア」を色々試せるようになったので、特に優先度はつけていなくてとりあえず実装してみてスコアを計算する、といった戦略になっています。

質問9.
AHCの10日間コンテストで、スコアが伸びない・アイデアが停滞したとき、どのように打開していますか？

saharan
苦しみます。とにかく考えられる方針を実装しやすいものからできるだけ多く試していきます。やや hacky ですが、相対スコアを利用して、どの傾向の問題でスコアが取れていないのかを見て伸びしろを分析します。Psyho のツイート (https://x.com/FakePsyho/status/1605570944537280512) を思い出します。1 位のスコアから、解がどのような状態になっている必要があるかを分析します。風呂に入ります。

montplusa
基本的には、将来性のある解法を序盤にできるだけ慎重に考えます。実装中の心づもりとしては、「まだこの部分は詰め切っていない」という部分を常に持っておき、終盤までは完全に詰まることがないようにしています。なんとなく届かなさそうなときはほかの可能性を探ってはいますが、そこは降りてくるかの運頼みなところがあります。

tomerun
そのような状態になってから打開できたことはないような気がしますね…

siman
スコアが伸びない、アイデアが停滞したときにやることですが、地道ですがやはり各テストケースを分析して、スコアが出るケースと出ないケースのビジュアライズ結果を比較していくのが大事だと思います。 「どういう条件なら高スコアになるのか」を調べられるように、様々なパラメーター（問題特有のやつ, ex) フィールドの広さ) を可視化出来るようにして、高スコアを取るための条件を整理していく感じです。 また、制限を無視した場合にどうなるのかを実験したりもします。例えば制限時間が 2secなところを 200secにして時間をかければ高スコアが取れるのかとか、何か制約を緩くしてみてその条件なら高スコアが取れるのかとか、とにかく今上位が取っているであろうスコアはどうすれば追いつくことが出来るのかをひたすら考える感じです。

質問10.
お気に入りのヒューリスティックコンテストの問題と、その理由を教えてください。

saharan
Exploring Another Space (AHC022) とても好きな推定問題で、理論が綺麗にハマってきちんと強い、という点がお気に入りです。同じ理由で Polyomino Mining (AHC030) もお気に入りです。

montplusa
AHC033 複数クレーンを用いて荷物の移動を行う問題ですが、最上位の所要ターン数がクレーンの諸々の条件を無視して移動距離だけで見た下界にかなり近いため、下界からのロスを考えると自然と良い評価関数になる、お手本のようなビームサーチ問題でした。

tomerun
北大・日立新概念コンピューティングコンテスト2018：固い数式と思いきや非自明パズル要素が多く、ヒューリスティックな探索要素もありで面白かった

AHC022：人々のビジュアライザのバリエーションが多くて見ていて楽しい。長期にしては実装量が少なく、実行速度による差があまりないのもよい

siman
AHC008 長年やっていると「焼きなまし」とか「ビームサーチ」が食傷気味になってしまうので、それらがメインの解法になりづらい問題固有の特化した解法が有効な問題が好きです。

おわりに

「自分はこうやって攻略しているよ！」といった情報がありましたら、ぜひtwitterの返信かリツイートでお願いします！また、もしアンケートを答えて知見を共有したい素晴らしい方がいらっしゃいましたら、ぜひDMください！