※本記事には解法のネタバレが大いに含まれます。閲覧にはご注意ください。
はじめに
こんにちは！AtCoder Heuristic Contest楽しんでいますでしょうか？
先日はAtCoderさん主催のAHC初心者向けオンサイトイベント「AtCoder Heuristic First-step Vol.1」の講師役として解説をさせて頂きました。
私の貪欲法解説スライドやtakumi152さんの焼きなまし法解説スライドもありますので、是非ご覧ください！
さて、こうやって各手法を学んだ初心者の方が次に直面する壁は「原理は分かったけど、実際の問題にどうやって適用すればいいのか分からない」だと思います。ABCの各種アルゴリズムも同じですよね。「アルゴリズムを知っている」と「そのアルゴリズムを使いこなせる」の間には大きな壁が存在します。
そこで実際の問題で練習を重ねていく必要があるわけですが、いきなりAHCの過去問で新しいアルゴリズムの練習をするのは結構ハードルが高いです。理由はAHCは超上級者の間でも差が付くように作られているから。
もちろんAHCは初心者でも楽しめるように作られていて、やれること・楽しめることはたくさんあるのですが、「焼きなまし・ビームサーチをそのまま適用すればOK」とはならないようにひねった問題が出されるため、これらの手法の勉強を目的としている人にとっては難しいことが多いです。
そこで練習問題としてオススメなのが「日本橋ハーフマラソンの予選問題」です。理由はこんな感じです。
- オンサイトコンテストの予選問題という性格上、一定以上のレベルかどうか判定することが目的となるので、素直な問題が出されやすい
- 4時間で2問解く超短期コンテストなので問題がさほど重くなく、短いサイクルで練習できる*1
- AHCが始まる前は今ほど焼きなまし・ビームサーチといった手法が広まっていないため、高順位相当の得点が取りやすい*2
ヒューリスティック問題は取り組もうと思えば1つの問題を無限にしゃぶりつくせるのですが、初心者のうちは解説を見ながら焼きなまし法・ビームサーチを実装してみて、ビジュアライザを見てみて「すげー！」となるところまでやれば十分でしょう。当時の上位スコアを目指すのはいろいろ物足りなくなってからで十分です。
解説が見つかりづらいというデメリットはあるのですが、できる範囲で探してきたり、ChatGPTに考えさせたりしたのでそちらも参考にして頂ければと思います。*3 また、コンテスト上位のコードをChatGPTなどのLLMに解説してもらうのもオススメです。*4
AHCの問題は入れていませんが、Hack To The Futureや企業対抗 Team Battleなどハーフマラソン以外の問題も紹介していきます。各問題に難易度を付けていますが、これはなんとなくで付けたものなので参考程度に。
というわけで、早速練習問題の紹介に入っていきましょう。
【2025/05/06追記】
tomerunさんが天才貪欲版をまとめてくださっています。こちらもあわせてどうぞ！
topcoder-tomerun.hatenablog.jp
焼きなまし
AtCoder Contest Scheduling（難易度★☆☆☆☆）
いきなりハーフマラソンじゃない問題を持ってきてしまいましたが、やはり一番オススメなのは Introduction to Heuristics Contest でしょう。いくつかの小問題に分かれていて、ABCのような小問題を解きながらAHCの取り組み方をステップバイステップで学ぶことができるのでかなりオススメです。
小問題・解説はこちら。
取り組むときは、
- A問題の問題文を読む
- B問題でスコア計算を実装してみる
- C問題でスコアの差分計算を実装してみる
- A問題に戻り、C問題で紹介されていた局所探索法（山登り法）を実装してみる
- 山登り法を焼きなまし法に変えてみる
- 公式解説を読み、より良い近傍操作（焼きなまし法の変形操作）を学んで実装してみる
という流れが良いでしょう。またこの問題に限りませんが、アルゴリズムの勉強中に途中で詰まったら割とすぐに解説を読んでしまって良いと思います。
注意点として、公式ビジュアライザの使い方が普段のAHCと違うのでREADMEをよく読んで使ってみましょう。誰かweb版ビジュアライザ作って
追記: thunderさんが爆速で作ってくれました！
ツーリストXの旅行計画（難易度★★☆☆☆）
touristです。ABCでも くらいでおなじみの巡回セールスマン問題っぽいのですが、距離ではなく辺の長さの分散を最小化する問題です。とはいえ普通の巡回セールスマン問題と同じアプローチが有効です。焼きなまし法を使って解く場合は「2-opt」で調べてみると幸せになれるでしょう。分散の計算方法も色々あるので、調べてみると今後のAHC含めて役にも立つかもしれません。
マッサージチェア2021（難易度★★★☆☆）
比較的新しめの問題です。比較的素直な焼きなましで結構良いスコアが出ます。焼きなましすげー！
なんとtomerunさんによる解説放送があります！豪華！
山型足し算（難易度★★★☆☆）
Hack To The Future予選の問題です。8時間コンテストですが、問題自体は比較的素直です。
こちらはtsukammoさんの解説記事があります。問題自体は7年前のもの*5なのですが、ちょうど先月スコアの更新もあったようで激アツです！
tsukammoさんのQiita記事は勉強になるものが多く、私も初心者の頃大変お世話になりました。必見です！
Turn Right（難易度★★★★☆）
「これ焼きなませるの！？」枠です。なかなか焼きなましという発想に至るのは難しいのですが、実装はそこまで重くないので是非解いてみてみてください。
これは企業対抗のチーム戦として実況中継されていて、ぼくが苦しんでいる姿を見ることができるので暇な人は観てみてください。
Multiple Pieces（難易度★★★★★）
こちらはグリッド上で各ピースの連結性を保たなければならないという制約があり難しいです。焼きなましに慣れてきたら是非チャレンジしてみてください。
maspyさんの解説記事は焼きなまし法ではなく、いわゆる乱択貪欲と呼ばれるものとなります。1つの問題に色々なアプローチがあるヒューリスティック問題の面白さが表れていると思いますので、そちらも読んで頂けると面白いでしょう。
- ChatGPT - 焼きなまし法による解法
- ピースの生成でBFS/DFSを行う際は BFSを繰り返すときに訪問済みかを記録する配列を毎回初期化しなくて良くするアレ - TopCoderの学習のお時間 を使うと高速です。
- [ハーフマラソン] Multiple Pieces（RCO 日本橋ハーフマラソン予選 [A]） | maspyのHP
- RCO presents 日本橋ハーフマラソン 予選 - posfie
Steiner Space Travel（難易度★★★★★）
手前味噌かつAtCoderではなくyukicoderの問題なのですが、以前私が出題した問題です。巡回セールスマン問題をちょっとひねった問題設定になっています。
普通の巡回セールスマンと違って順番だけでなく宇宙ステーションの位置も決める必要があるのですが、そのようなときの焼きなまし方法について学べます。普通の焼きなましより難しいチャレンジ問題枠です。
ビームサーチ
AtCoder Contest Scheduling（難易度★★☆☆☆）
焼きなまし部門に続いて2回目。ビームサーチの練習問題としてもシンプルでオススメです。ただ公式解説がないんですよね……。
こちらの解説記事がオススメです。簡潔ですが、貪欲法との対比になっていて分かりやすいです。
ゲーム実況者Xの挑戦（難易度★★★☆☆）
マップを 個選ぶパートが難しいですが、ビームサーチの練習であれば適当に決めちゃってOKです。
こちらはthunderさんが丁寧な記事を書いてくださっています。
thunderさんはAHCで頻出の探索手法をまとめた本も出版されています。クラスや構造体に分けて綺麗なコード書くという長期AHCでとても重要なスキルを学ぶこともできるので、ガッツリAHCをやってみたいという方は是非買ってみましょう。thunderさんが喜びます。
カラフルパネル（難易度★★★★☆）
Chokudai Contest、通称大根の問題です。評価関数をどうするかも考え甲斐があります。誰かweb版ビジュアライザ作って
ゲーマーXとモノス大会（難易度★★★★☆）
パズルゲームのような問題です。評価関数を工夫するとスコアが伸びるので、そういった工夫の練習にもなるでしょう。
ちなみに焼きなましで解くこともできるようです。
Volume Control（難易度★★★★★）
これも企業対抗 Team Battleからです。操作の候補を全部試すと多すぎるという場合に、どのようにすればよいかについて学べます。応用的な工夫が求められます。
こちらも実況中継がなされています。苦しかった……。
おわりに
ABCでは典型アルゴリズムの練習用問題が有志の記事によってまとめられていますが、AHCでは今までほとんど見たことがなかったな……と思って書いてみました。
「AHCに興味を持ったはいいが、どのように典型アルゴリズムを練習すべきか分からない」という方のお役に立てれば幸いです。
*1:Hack To The Futureの予選問題もオススメなのですが、8時間コンテストなのでやや重めです。
*2:モチベーション管理はめちゃくちゃ大事です。今まで取ったことのない順位を取って自己肯定感を高めていきましょう。
*3:このくらいの難易度であればChatGPTくんも悪くない方針を考えてくれます。また、方針が微妙だったときはこちらからアドバイスを加えて軌道修正しています。
*4:例えばこんな感じで、問題文とコードを貼り付けて雑に聞いてみるとよいです。 https://chatgpt.com/share/67f9cb98-28fc-8001-8bd3-23bdfd6002e2
*5:2025/4/13現在
