はじめに
本記事はAtCoderのヒューリスティックコンテスト(通称AHC)で問題に取り組む際の考え方やヒントを筆者の経験をもとにまとめたものです。
ヒューリスティックコンテストでは、ビームサーチや焼きなましといった典型的な手法がよく使われます。しかし、最近のAHCではこれらの手法に素直に持ち込めない問題も増えています。筆者は2年ほど前に競プロ〜ヒューリスティック/マラソン事始め〜という記事で、どの手法に持ち込めば良いかという考え方を紹介しましたが、それだけでは対応が難しい問題が増えていると感じています。
本記事ではこうした状況を踏まえ、少しでも参考になるような「ヒント」を紹介していきます。
想定読者
- アルゴリズムコンテストに参加し他ことがあるが、ヒューリスティックコンテストは未経験の(または挫折した)方
- ヒューリスティックコンテストの初級〜中級者
題材に取り上げた問題の細かい説明は省略しています。
詳細はリンク先の各問題の問題文をご覧ください。
考察編
1. 粗視化する
盤面サイズが200 × 200で水路を掘り進める問題です。以下のような特徴がある問題です。
- なるべく色の薄い掘りやすいルートを見つけたい
- 掘りやすいかは掘ってみないとわからない。道を掘り進めて固い岩盤に当たるとそこまで掘った分が無駄になる
- よって、まずは大雑把にどこが通れるのかを把握できると嬉しい
粗視化のアプローチ
「大雑把に良さそうな解を探す」ために役立つのが粗視化(粗く見ること)です。200 × 200の盤面を20 × 20の格子に分割し、まずは格子点だけを掘ることを考えましょう。色の濃いエリアと薄いエリアはある程度固まっているので、格子点だけしか掘らなくてもその周りの様子を推測することができます。
粗視化することで大雑把に良さそうな解を「効率的」に求めることができます。この問題の場合は「効率的」というのは、掘る回数を減らせるということでスコア改善につながるわけですが、問題によっては以下のようなメリットが得られる場合もあります。
- 計算量を減らせる
- 大局的に良い解を求められるので、(大局的には良くない)局所最適解を回避しやすい
その他の粗視化例
-
THIRD プログラミングコンテスト2024 (AHC039) Purse Seine Fishing
広大な10万 * 10万の盤面を粗く分割し、計算量を大幅に減らす。
2. 小問題に分割する
信号の切り替え回数を少なくする旅行ルートを求める問題です。信号の切り替えに使う数列Aも自分で決められるので、数列Aを調整しながらルートを探索することで最適化ができるのではないかと思えます。
筆者も最初はそう考えましたが、数列Aのサイズの制約からうまく実装するのは難しいことに気付きました。そこで問題を2つに分けることにしました。
- 巡る順序を無視して配列Aを決める問題
- 与えられた配列Aで信号の切り替え回数を減らす問題
- メリット： 問題が単純化される
- デメリット： 全体を考えることによる最適化が犠牲になる
問題が単純化されるというのはそれほどメリットがあることなのでしょうか？筆者の場合、付随して以下のようなメリットが得られました。
- 数列Aを決める際の発想が転換できた
- 例えば、メインストリートを格子上に作って効率的に動けるようにする等
- 実装が簡単になった
複雑な問題に直面したとき、独立した小問題に分割して単純化するのは有効なテクニックの一つだと思います。
その他の問題分割例
-
トヨタ自動車プログラミングコンテスト2024#5(AHC033) Container Handling with Cranes
コンテナの順序や一度置くかどうかを決めるパートと、クレーン操作を決めるパートに分ける
3. 自主的に制約を追加する
オフィスに仕切りを作って、ペットと社員を分離する問題です。
今回のアプローチは、自由度が高すぎる問題に対し、自分で制約を設けて考えやすくするというものです。
筆者は以下のような「自主制約」を設けて解くことにしました。
- あらかじめ決まった位置に壁を作り、小部屋候補を多数用意する
- 社員は赤い通路のみを移動する
- ペットが小部屋に入っていたら緑のマスに壁を設置して閉じ込める動きに限定する
「自主制約」による効果は以下のとおりです。
- メリット： 考えるべきことが明確になり、アプローチが具体的になる
- デメリット： 何の制約もなく解く場合に比べて得られるスコアが低くなる可能性がある
この考え方は、先ほど紹介した「粗視化」や「小問題分割」とも共通しています。これらも主制約の一種とも言えます。「粗視化」や「小問題分割」直感的に理解しやすく、頻繁に使われる手法であるため、最初に紹介しました。
自主的に制約を設けるというのは勇気がいるものです。しかし、何も制約を設けず自由に考えてどこから手をつけて良いかわからない状況を、制約を設けて問題を具体的に考えられるようにするというのは大きな前進です。もし仮にうまくいかなかったら、別の制約を考えれば良いだけです。
筆者自身もこのアプローチで初めてAHCで20位以内に入ることができました。
その他の制約例
-
HACK TO THE FUTURE 2025(AHC040) Packing Uncertain Rectangles
箱を入れる方向は自由だが1方向のみに制限する。箱の置き方も階層的に置くことだけを考える。
4. アルゴリズムの知識で解ける範囲を探す
クレーンを使ってコンテナを所定の順番で出口に運び出す問題です。先ほど「小問題分割」の例でも挙げましたが、実は分割した「運ぶコンテナの順序や一度置くかどうかを決めるパート」は、アルゴリズムの知識を活用することで厳密解を求めることができます。具体的には、一度置くコンテナを最小化する問題としてDPを使って解くことができます。
ここまで説明してきた「粗視化」「小問題分割」「自主制約」は、アルゴリズム知識で厳密に解ける部分を作ることにも役立ちます。
- 粗視化： 計算量が減り、現実的な計算量で厳密解を求められるようになる
- 小問題分割： 分割した問題の一部が厳密に解ける
- 自主制約： 制約を課すことで問題が単純化され厳密解が求まる
このように、アルゴリズムの知識で解決できる部分を切り出すことで、残りの部分に集中して取り組むことができます。
その他のアルゴリズムで解決する小問題
-
RECRUIT 日本橋ハーフマラソン 2024夏(AHC036) Efficient Signal Control
配列Aが与えられた場合に、最短手数で目的都市を巡る問題は01BFSの応用で解ける(ただし配列Bへの取り出し方に一定の制約を設けた場合) -
RECRUIT 日本橋ハーフマラソン 2022夏(AHC013) Server Room
同種のコンピュータを連結させるフェーズや、コンピュータを接続させるフェーズでBFSや耳DPなどのアルゴリズムが使える 参考：RECRUIT 日本橋ハーフマラソン 2022夏(AHC013)27位解法
5. 実行時間を活用する
ヒューリスティックの問題では、2秒や3秒といった実行時間を有効活用することが非常に大切です。
自分が作った解法が一瞬で実行できてしまうなら、実行時間をうまく活用できないか考えてみましょう。
図に挙げたのは、粗視化の例でも挙げた魚群を網で囲む問題です。
筆者は以下のような解法を考えました。
- 粗視化してマスごとの魚の数を求める
- 魚が多いマスから順にDijkstra法でマスをつなげる(粗視化したことにより計算量が削減され、実現できた)
- 網の長さが足りなかったらつなげるのを諦める
これでもある程度のスコアは出ましたが、実行時間が大幅に余っていたため、次の工夫を加えました。
- 格子のサイズをいろいろと変えて時間一杯試す
この実行時間の活用により、スコアを5%以上改善することに成功しました。
焼きなましやビームサーチといったヒューリスティックの典型手法以外でも、実行時間をうまく活用することでスコアが改善できる場合があります。
- 解くのに使用しているパラメータを変えて試す
- 解法にランダムで変わる要素を入れて繰り返し試す
この手法はいわゆる山登り法とも似ています。山登り法は典型的には解を少しだけ変えて試すことが多いですが、上記のように大幅に変えて試すだけでも十分に効果があります。
実行時間が余っているなら、ぜひ活用を考えてみましょう。
マインド編
アルゴリズムでもヒューリスティックでも、コンテストには2種類の時間制限があります。
- 実行時間： １つのケースに対するプログラムの実行時間(通常2〜3秒)
- コンテスト時間： コンテスト全体の終了までの時間(ヒューリスティックでは4時間〜2週間が一般的)
ヒューリスティックではコンテスト時間が長いため、実装にかかる時間は軽視されがちです。しかし、仕事や学業など社会生活を送りながらコンテストに取り組むことを考えれば、時間を有効に活用するのは大切です。
ヒューリスティックコンテストでは以下のようなことが起きがちです。
- 思いついた解法を一生懸命実装したが、スコアが悪化した
- 思いついた解法の実装が重すぎて、いつまで経っても実装が終わらない
前者であればいち早く気づいて別のアプローチをしたいですし、後者は精神衛生上よくありません。
ヒューリスティックコンテストでは、さまざまな手法を試すことが強い解法へとつながる重要な要素です。そのため、軽く実装してダメなら別の方法に切り替える、というサイクルを回すという考え方が大切です。
以降では、無駄に実装時間をかけないようにするための心構えをいくつか書いておきます。
6. 高速化は後回し
アルゴリズムのコンテストでは、計算量を削減するために効率の良いアルゴリズム(例：二分探索、セグメント木)を用いるのが定石です。しかし、ヒューリスティックの問題では一般的に入力制約が小さめなので、愚直に実装をしてもTLEにならないことが多いです。
まずは計算量を細かく気にせず、例えば愚直なループで実装してしまいましょう。
その後、本当に高速化が必要な状況(例：実行時間一杯試してスコア改善しているがもっとたくさん回数を回したい)になってから高速化を図れば十分です。
7. コーナーケースに囚われすぎない
アルゴリズムコンテストではコーナーケース対策が重要ですが、ヒューリスティックコンテストでは少し事情が違います。
ヒューリスティックではテストケースの入力がランダム生成されることがほとんどであり、意図的にコーナーケースを狙い撃ちされることは基本的にありません。コーナーケースを無視して良いとまでは言いませんが、アルゴリズムコンテストほど厳密な対策は不要と言えます。
コーナーケースに当たってWAとなってしまった場合の取り扱いをもう少し詳しくみてみましょう。コンテストによって以下の2パターンがあります。
- 不正な出力のケースだけが0点となり、他のケースのスコアは有効(長期コンテストに多い)
- 不正な出力が1つでもあれば提出全体が無効(短期コンテストに多い)
したがって、コーナーケースへの対処として、以下のスタンスを取ることが可能です。
- 長期コンテスト
- ごく稀なケースは諦める(1000ケースに1回程度であれば影響は0.1%)
- 最小限の回避策だけを考え、細かい対応に時間をかけすぎない
- 短期コンテスト
- 提出してみてコーナーケースに当たらなければそのまま無視する
- 当たってしまった場合は最小限の回避策を考える
ここで言う「最小限の回避策」とは、極端な話、ヒューリスティックコンテストで最初によくやる「正のスコア」を得るための自明実装でも構いません。
例えば、最初に安全で最小限の有効な解を作っておき、それをエラー回避用の保険としておくだけでも十分です。
コーナーケース対策を厳密にすることに時間を費やすよりも、何か別のスコア改善を目指していきましょう。
8. 嘘解法でも良い
アルゴリズムで「嘘解法」という言葉を聞くことがあります。明確な定義は定かではありませんが、「多くの場合正しい解を出すが誤った解を出す可能性もある解法」を指すものと思われます。
アルゴリズムのコンテストに慣れている方は「嘘解法」は避けるべきものと捉えることが多いと思いますが、ヒューリスティックコンテストでは必ずしもそうとも限りません。
ヒューリスティックは理論的な最適解が求まるような問題は出題されないので、そもそもコンテスト自体が「より良い嘘解法」を競う場であるとも言えます。
そんな状況ですから、ある小問題に厳密解が存在するとしても、実装が面倒ならば一旦「嘘解法」で済ませるのも一つの手です。もちろんWAを頻繁に起こす原因になるような嘘解法は問題ですが、たまにスコアが少し悪化する程度のものであれば十分実用範囲です。
9. 一歩ずつ進める
プログラムを動かしてビジュアライザーを眺めていると、改善したい点がいくつも思いつくことがあります。そんなときにまずやることは、思いついたことを箇条書きでメモしておくことです。
メモした改善は一気に全部実装するのではなく、1つずつ進めるのがポイントです。複数の改善を同時に行うと、思いがけない副作用があって、どの変更がいけなかったのかわからなくなり、調査に時間を浪費することになるかもしれません。
また、1つの改善が大掛かりな場合も、小分けにできないかを検討しましょう。常にプログラムが動く状態を保ちながら少しずつ進める方が、精神衛生上も良いです。
10. 拡張性は後回し
ヒューリスティックの問題はアルゴリズムコンテストと比べて大掛かりな実装が必要になることが多いため、しっかり設計しプログラムに拡張性を持たせることが後々重要になります。しかし、最初から「拡張しやすい設計」を意識すぎると、時間と労力を無駄にしてしまうことがあります。
実際にプログラムを作り、ビジュアライザーで動きを確認してみると、拡張の方向性が当初の予想とは異なることも少なくありません。最初から考慮していた設計が無駄になってしまうともったいないので、必要に応じてリファクタリングする方が効率的です。
ただし、必要になった段階でのリファクタリングは積極的に行いましょう。目先の改善点に集中できるように、それとは関係ない細かい処理を別関数や別クラスに切り出すことで、改善に向けた試行錯誤の効率が格段に上がります。
おわりに
本記事では、ヒューリスティックコンテストに取り組む上での考え方やヒントを、筆者の経験をもとにまとめました。本当は「考察典型」のような形で整理したい気持ちもありましたが、そこまで体系的にまとめることは難しかったため、ヒューリスティック精神に則ってまずは「ヒント」という形で第一歩を踏み出してみました。
ヒューリスティックコンテストについては、ビームサーチや焼きなましといった手法についての解説記事は充実してきていますが、考察の進め方に関する記事はまだ少ないように感じます。この記事をきっかけに、より多くの考察方法や典型パターンが共有されるようになると嬉しいです。