ヒューリスティック問題を解く

ヒューリスティック型の問題に関する記事を以下の観点でカテゴリ分けしています。

入門者・初心者向け
コンテストに参加する
資料集
典型的な手法の解説と応用

参考

カテゴリやサブカテゴリによっては、中・上級者向けの内容も含まれています。難しすぎる内容だと思ったときは、少し時間を置いて読み直してみましょう。

入門者・初心者向け

典型的な問題と実生活

数理最適化ことはじめ - 数理最適化を概観し、基本的な問題とその解き方を分かりやすく解説したスライド。豊富な図解や社会での活用例が掲載されているのが特徴。
AHC001の知識とpythonの力で、奇想の浮世絵師「歌川国芳」の絵を再現する - 浮世絵師・歌川国芳風の寄せ絵の制作過程、使用技術の概略、寄せ絵・だまし絵を得意とする画家を紹介した記事。猫の絵を敷き詰める際に、AtCoder Heuristic Contest 001の知識が活用されている。
メタヒューリスティクスで広がる「解けた！」の世界 - メタヒューリスティクスの概説、解けるようになる問題例と代表的な手法、実社会への応用例などが紹介されている。
アルゴリズムで実社会を捉える～評価関数の作り方～ - 競技プログラミングにおけるゲームAI系のコンテストを題材に、筆者が評価関数を作成するときに意識していることを紹介した記事。評価関数の説明から、実社会の問題をアルゴリズムで解くときに人間の感覚を評価関数に反映させるための考え方やその意義について解説されている。

コンテストの面白さ・楽しみ方

AHC(AtCoder Heuristic Contest)はいいぞ - AtCoder Heuristic Contestへの参加を布教している記事。筆者のおすすめポイントが紹介されている。
競技プログラミングにおけるマラソン系コンテストの楽しみ方 - ヒューリスティック型コンテストの楽しみ方を、点数・visualizer・感想戦の観点から紹介した記事。
競技プログラミングにおけるゲーム木探索の面白さ - 実例をもとにゲームAI系コンテストの魅力・面白さを紹介した記事。
みんなAHCの魅力を知らなすぎて困る - AtCoder Heuristic Contestの魅力・おすすめの理由が語られている記事。次のコンテストに参加するまでにできることも紹介されている。

問題を解く

直感でわかる、ヒューリスティック問題の羅針盤～貪欲法から山登り法まで～ - ヒューリスティック型コンテストの代表的な手法である貪欲法と山登り法を解説した記事。手計算で問題を解きながら、自分の直感で考え、プログラムとして実装できることの重要性が示されている。
Introduction to Heuristics Contest 解説 - Introduction to Heuristics Contestで出題されたスケジューリング問題を題材に、問題に対する取り組み方と典型的な手法が紹介されている。サンプルコードは、Rustで実装されている。

最初の解法を思いつくには?

マラソンマッチの簡単な解法 - ヒューリスティック型コンテストの初心者に向けて、最初の解法を思いつくまでの着眼点(パラメータの扱い方、計算結果の再利用、部分的な最適化)を紹介した記事。
競プロ解法紹介～レベル別マラソンの戦い方～ - マラソン形式の問題であるHack To The Future 予選問題を題材に、初心者から上級者までを対象として、それぞれのレベルに応じた戦い方を紹介した記事。

入出力データの管理

ヒューリスティック初心者の取り組み方 - ヒューリスティック型コンテストの参加希望者・初心者に向けて、大量の入出力を扱う方法を解説した記事。C++で実装されたサンプルもある。
AHCのローカルテスト環境構築 - ローカル環境で複数のテストを実行するための方法が紹介されている。
AHC(AtCoder Heuristic Contest)で、手元で100テストケースを自動で試す(Linux) - ローカル環境で多数のテストケースを実行する必要性とその方法を解説した記事。
AHC(AtCoder Heuristic Contest)のテスト用スクリプト - 複数のテストを手軽、かつ、高速に実行するためのシェルスクリプトが紹介されている。
AHCで手元で複数ケース実行するためのスクリプト - 複数のテストケースを一度に実行して、スコアを集計できるPythonスクリプト。

コンテストに参加する

取り組み方(心構え)

マラソンマッチにおける精神論 - ヒューリスティック型コンテストでスコアを上げるために、地道な改善を根気よく続けることの重要性を指摘している記事。

取り組み方(技術)

マラソンマッチで気をつけるべきこと - 2週間程度のヒューリスティック型コンテストを対象として、筆者の戦略を紹介した記事。
マラソンマッチで最初の12時間にすべきこと - ヒューリスティック型コンテストにおいて、hamaduさんが普段の取り組みで気をつけていることを紹介した記事。
マラソンマッチの取り組み方 - ヒューリスティック型コンテストの取り組み方について、3つの観点(問題の把握・判断基準の明確化・反復期間の短縮)に集約して説明した記事。
Psyhoさんによるヒューリスティック・ボットコンテストのための無料Tips - PsyhoさんがTwitterに投稿したヒューリスティック/ボットプログラミングコンテストに関する知見を、日本語に翻訳してまとめている記事。
Marathon Matchでいつもやってること - tomerunさんが、ヒューリスティック型コンテストに関するノウハウをまとめた記事。
rhooさんによるヒューリスティックコンテストの汎用テクニック集 - ヒューリスティックコンテストにおける汎用的なテクニック（焼きなまし法・ビームサーチ・評価関数・高速化など）が簡潔にまとめられている。
北大日立新概念マラソンでやった高速化色々 - ヒューリスティック型のコンテストにおいて、アルゴリズムの側面から高速化に関する知見の一般化を図った記事。
マラソンマッチにおける頻出Q＆Aと小技 - ヒューリスティック型コンテストのうち、最適化問題における疑問点やコツがQ&A形式で簡潔にまとめられている記事。

注意

本記事を読む前に、マラソンマッチの取り組み方などの記事を読み込み、何回かコンテストに参加することが推奨されている。

取り組み方(実装)

AHC 典型: 解をたくさん作る - ヒューリスティックコンテストで、貪欲法の次に試すアプローチ方法が紹介されている。
AHC典型解法シリーズ第1弾「モンテカルロ法」 - AtCoder Heuristic Contestの解法の分類により、典型的な手法の抽出とその重要性が指摘されている。また、モンテカルロ法と過去問への適用例が紹介されている。
- AHC典型解法シリーズ第2弾「焼きなまし法」 - 典型的な解法をまとめたシリーズの第2弾。コンテストの過去問を例題に、焼きなまし法の適用するときの工夫が解説されている。
マラソン系コンテストでソースコードを分割して書く方法のメモ(C++) - コンテストで快適にコーディングできるように、開発時にはソースコード(C++)を複数のファイルに分割して記述し、提出時に1つにまとめて提出する方法が紹介されている記事。
- サンプルコード
ヒューリスティックコンテストで機械学習しよう - コンテストで統計的な手法を検討したい場合に、典型的な問題とその実装例が紹介されているスライド。
Rust 競プロ AHC参加の準備してみた（チートシート集） - Rustでヒューリスティック問題を解くときに、つまづきがちな点をまとめたチートシート。実行制限時間の設定方法、乱数の生成・利用、演算子のオーバーロード(ビームサーチの実装で構造体同士の比較に必要)が紹介されている。
Rustでマラソンをするときに使えそうなスニペット達 - Rustでヒューリスティック問題を解くときに便利なスニペット集。乱数生成、ハッシュ関数、個数制限付きヒープ、値の複製・追加が高速にできるリストが紹介されている。
8近傍だけで連結性を良い感じに確保し続ける典型 - グリッドの特定のマスを中心とした8近傍を利用し、連結性を確保し続けられる典型テクニックが図解されている。

参加記・解法の解説

競プロ解法紹介～大局観で高得点を取る！～ - マラソン形式の問題であるChokudai Contest 001の解法を紹介した記事。愚直な解法から高得点を狙うための着眼点や方法が解説されている。
AtCoder Heuristic Contest 001 - じろうのブログ - JirotechさんによるAtCoder Heuristic Contest 001の解答方針と、得点の増加につながった考え方・指標・調整方法などを紹介した記事。
AtCoder Heuristic Contest 001 (AHC001) 初心者向け解説 - terry_u16さんが、ヒューリスティック型のコンテスト初心者に向けた解説・Tipsを紹介している記事。
- THIRD プログラミングコンテスト2023 (AHC030) 解説
- HACK TO THE FUTURE 2022 本選オープン解説＋参加記
AtCoder Heuristic Contest 001 AtCoder Ad - びったんびったん - hakomoさんによるAtCoder Heuristic Contest 001の解答方針と頻出テクニックを紹介した記事。
AHC003の2.926T解法+経緯 - eivourさんが、AtCoder Heuristic Contest 003での最終解法と、その経緯などを紹介した記事。また、HACK TO THE FUTURE 2022予選に関する記事も公開されている。
実録！AtCoder Heuristic Contest 011参加記 - kaede2020さんの参加記。良い得点を得るために試行錯誤する過程がリアルタイムで記録されている。
- MC Digital プログラミングコンテスト2024（AtCoder Heuristic Contest 031）参加記
参加記の一覧
AHCガチ素人のアルゴ茶コーダー VS AHC013 〜初歩的アルゴ知識だけで戦ってみました〜 - fujikawahiroakiさんの参加記。アルゴリズム部門で身につけた知識を活用して、コンテストに挑戦する過程がまとめられている。
- AHC016（HTTF2023予選）敗戦記　〜傷まみれの青春〜
AHC018の1位解法(Psyho氏の解法)解説 - PsyhoさんによるAtCoder Heuristic Contest 018の解答方針を、thunderさんが詳しく解説した記事。
- TOYOTA AHC 至高のアルゴリズム解説会 AHC015 - AtCoder Heuristic Contest 015の延長戦1位(2024年1月末時点)の解法を紹介・解説した記事。
AHC018 ガウス過程回帰を用いた解法 - 観測された情報から未知の情報を推定するガウス過程回帰の説明を中心に、AtCoder Heuristic Contest 018への適用例も紹介されているスライド。
【AHC022】 AHC初参加記〜入茶しました - Likafさんの参加記。AtCoder Heuristic Contest 022に参加した経緯、考察内容やスコアの推移、感想などがまとめられている。
第10回 Asprova プログラミングコンテスト参加記 (39.1M; 130位) - nishigakeさんの参加記。AtCoder Heuristic Contest 023で、最初の解法から「改善案を考え、実装する」サイクルを繰り返して高得点を目指している記事。
トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）至高のアルゴリズム解説 - AtCoder Heuristic Contest 026を対象として、延長戦の解法が2種類解説されている。
AHC030のseed0のバババッて決まるやつは結構簡単に作れるよという話 - AtCoder Heuristic Contest 030を題材に、ベイズ推定の概略とC++の実装例が紹介されている。
- 相互情報量を学んでもっとうまくAHC030を解こう！ - 上記の記事の続編。相互情報量を最大化するような点集合を選択することの具体的な意味とC++実装例が紹介されている。
第一回マスターズ選手権予選・参加記 - 第一回マスターズ選手権-予選-の参加記。問題の解法、高得点を取るための工夫が時系列でまとめられている。
世界一やさしいAHC体験記 - buriodenさんの体験記。ヒューリスティック型コンテストに興味がある人に向けて、筆者が初参加のコンテストで回答を提出するまでの流れや感想などがまとめられている。
FakePsyho/cpcontests - Psyhoさんが参加したコンテストの解答の方針とソースコードがまとめられている。

もっと読む

コンテスト企画者の振り返り

企画者目線で振り返るestie プログラミングコンテスト2022 - matsu7874さんが、企画・運営の立場からestie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）を振り返った記事。

ALGO ARTISプログラミングコンテスト writerインタビューアルゴリズムエンジニア松尾が語るコンテストの舞台裏 - ALGO ARTIS プログラミングコンテスト2023（AtCoder Heuristic Contest 020）のwriterであるterry_u16さんへのインタビュー記事。コンテスト開催までの経緯、問題の作成・調整の過程とコンテスト当日の状況などがまとめられている。

問題や参加者に関する調査・分析

競プロ〜ヒューリスティック/マラソン事始め〜 - ヒューリスティック型コンテストの問題を「改善重視型」「初期解重視型」「パラメータ推定型」に分類し、それぞれのアプローチ方法や高スコアを目指すためのテクニックが紹介されている記事。
AHC001（マラソンマッチ）の参加者の使用言語の分布を調べてみた - AtCoder Heuristic Contest 001で一定の得点以上の提出コードを対象として、利用者の多い言語、使用言語と得点・順位との関係を調査した記事。ヒューリスティック型のコンテストにおいて、使用言語を選択する際に参考になると思われる。
Atcoder Heuristic Contestの順位とアルゴリズムのレートの関係性を眺める - Ratedのヒューリスティックコンテスト(短期・長期)とアルゴリズムのレーティングとの関係性を調査・分析した記事。
AHC（の問題設定を現実に実行する場合の）難易度表 - ヒューリスティック型コンテストの問題設定を人類が実現しようする場合の難易度表。

注意

問題そのものの難易度ではない。

便利ツールの作成・活用

ビジュアライザを自作する

ヒューリスティックコンテストでビジュアライザを開発する方法に関するメモ - ヒューリスティックコンテストで使用するビジュアライザの開発方法が紹介されている記事。
- ReactとRustで実装されているテンプレート
- ヒューリスティックコンテスト用Visualizer(Rust, SVG) チートシート集
簡単＆便利！ C# × .NET Blazor で AHC ビジュアライザ作り - ヒューリスティックコンテストで使用するビジュアライザを自作する方法が解説されている記事。サーバサイドとクライアントサイドのロジックが、同じ言語(C#)で記述できるのが特徴。
- サンプルプロジェクト - AHC011

Optuna

Optunaでヒューリスティックコンテストを解く - ヒューリスティックコンテストでハイパーパラメータの調整を行う際に、Pythonライブラリ「Optuna」を利用する方法を紹介した記事。また、Python以外の言語(C++)で書かれたコードに対するパラメータの調整方法が丁寧に解説されている。
Optunaを使ってAtCoder Heuristic Contest 007を優勝する - AtCoder Heuristic Contest 007を題材に、ハイパーパラメータをPythonライブラリ「Optuna」で探索して高スコアが得られたことを紹介した記事。提出コードと各ツールの連携方法やパラメータの探索結果の可視化について解説されている。

AWS

AWS上にマラソンマッチ用のジャッジ環境を作った - ヒューリスティック型コンテストにおいて、大量のテストケースをAWS環境で処理する方法が紹介されている記事。
- 「AWS上にマラソンマッチ用のジャッジ環境を作った」をChatGPTに投げて、Lambdaを使ったAHC用のジャッジ環境を作る。 - ChatGPTによる質問・回答を繰り返しながら、AWS環境の構築過程とエラーへの対処方法が紹介されている。
注意

AWSに関する基礎知識が必要であり、各サービスの利用状況に応じて料金の支払いが発生する。

資料集

数理最適化

ヒューリスティック最適化資料集 - ヒューリスティックコンテストに関するリンク集と過去問がまとめられている資料集。
Python言語による実務で使える100+の最適化問題 - 典型的な最適化問題とそれらの定式化・解法が網羅されている。サンプルコードはPythonで実装されている。
局所探索法とメタヒューリスティクス - 組合せ最適化問題のうち計算困難な場合に対して、局所探索法やメタヒューリスティックスによるアプローチ方法を紹介しているスライド。
しっかり学ぶ数理最適化ヒューリスティック編 - 「しっかり学ぶ数理最適化モデルからアルゴリズムまで」の内容をベースに、視覚化に焦点が当てられている記事。

ゲームAI

世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門 - ゲーム木探索に関する入門記事。ゲームの種類(一人ゲーム・交互着手二人ゲーム・同時着手二人ゲーム)と対応する探索アルゴリズムがとても丁寧に解説されている。また、汎用アルゴリズムの実装例と動作可能なサンプルコードが両方とも掲載されているのが特徴。
オセロAIの教科書 - オセロAIの初歩から高度な内容まで解説されている記事集。C++とPythonで実装されたサンプルもある。

探索手法の解説と応用

chokudaiサーチ

chokudaiサーチ(ビームサーチ亜種)の利点の話 - 探索アルゴリズムの一種であるchokudaiサーチについて解説されている記事。Beam Stack Searchと比べて、時間管理が楽になることや探索の多様性を考慮できることに特徴がある。
- Chokudai search - 上記の記事の内容が簡潔にまとめられているスライド。

ビームサーチ

ビームサーチ講座 - 選択した順番によって結果が大きく変わる問題を解くときに、全探索と貪欲法の中間的なアプローチである「ビームーチ」を図解したスライド。

注意

実装に関しては、別の記事や書籍を読む必要がある。
ビームサーチの上位N件を高速に取る手法について考えてみる - ビームサーチで、表題の内容について高速化を図った記事。C++で実装された実験コードに基づいて、実行速度の計測・比較が行われている。
高速なビームサーチが欲しい!!! - ビームサーチの高速化について解説した記事。前提として、ビームサーチの基礎とC++のポインタなどの知識が必要。
- ビームサーチをライブラリ化する【基礎編】 - ライブラリ作成の方針・一般的な実装方法(C++)を紹介した記事。応用編もある。
- 爆速ビームサーチライブラリを作る - 典型的なケースに対応した高速なビームサーチの実装とライブラリ化の方法を紹介した記事。
  - Rustで実装されたライブラリ
ビームスタックサーチ（Beam-Stack Search）の解説 - ビームスタックサーチについて、原著論文をもとに解説した記事。上述のchokudaiサーチとは異なるアリゴリズムであると指摘されている。

焼きなまし法

誰でもできる焼きなまし法 - gasinさんが「焼きなまし法」の汎用性の高い実装方法を紹介した記事。
- 焼きなましをするときの設計に関するメモ - 焼きなまし法を利用するときのクラス設計とC++の実装例が紹介されている記事。
競技プログラミングにおいて焼きなまし法に堕ちずに落とすコツ - tsukammoさんが「焼きなまし法」を適切に利用するための知見をまとめた記事。相性の良い/悪い問題の特徴、同手法の適用範囲、問題の特性を活用したアプローチ方法が紹介されている。
焼きなまし法のコツ Ver. 1.3 - shindanninさんが「焼きなまし法」の使い方について、高速化・次の状態の決め方・評価関数などの観点から網羅的にまとめている記事。また、各項目について重要度が併記されているのが特徴。
焼きなまし法での評価関数の打ち切り - 焼きなまし法の判定条件を式変形することで、評価値が閾値を超過した時点で評価関数を打ち切る方法が紹介されている。
焼きなまし法の適用メモ - 焼きなまし法を問題に適用するときに、留意すべき事項(重要なパラメータ・適用の妥当性を判断・概念や用語)がまとめられている記事。
詳解焼きなまし法 - hakomoさんが、コンテストで高いスコア・順位を取るために、最上位陣による実践的な工夫と適用例の網羅を目指しているレポジトリ。

注意

最終更新が2018年11月末であり、一部の項目については準備中であると思われる。
焼きなまし法の真実 - 焼きなまし法に関する疑問点・コンテストを通して得られた知見が整理されている記事。

注意

前提条件として、焼きなまし法に関する一定程度の知識が求められる。

ベイズ推定

ヒューリスティックコンテストでベイズ推定に入門しよう - ベイズ推定を活用して、限られた情報からパラメータを予測する方法を解説した記事。AtCoder Heuristic Contest 003を題材として、C++での実装例も紹介されている。

シュタイナー木

プリム法ベースのシュタイナー木 - プリム法をベースとしたシュタイナー木に関するアルゴリズムが図解されている記事。Dreyfus-Wagner法と比べて計算量は少ないもののコストが最小になるとは限らないため、厳密さよりも速度が優先される場面での利用が想定されている。

ゲーム探索木

この木なんの木？　モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々 - モンテカルロ木探索を最良優先MiniMax探索に変える過程で存在する有用な木の概念を紹介した記事。