はじめに
今年からAtCoderでヒューリスティックコンテスト(マラソンマッチとも呼ばれています)が定例開催化され、少しずつ普及が進み始めた感があります。その一方、通常のアルゴリズムコンテストについては、「競プロ典型 90 問」や「アルゴ式」などの良質な勉強コンテンツが充実してきていますが、ヒューリスティックコンテストに取り組もうとしたときにどうして良いかわからないという方も少なくないのではないかと思います。
筆者も実は今年初めて参加し、まだ参加コンテストは8つというそれほど多くはない参加経験ではありますが、本記事ではヒューリスティックコンテストの問題のパターンを分類し、どういったアプローチで考えていけば良いかを整理してみたいと思います。
パターン分類と言ってもそれほど大仰なものではないですが、少しでもこれから取り組む方の参考になればと思っています。
対象読者
- ヒューリスティックコンテストに興味はあるけれども、過去問を見ても何を考えたら良いのかよくわからない人
- ヒューリスティックコンテストのエキスパートで、もっとこんなパターンがあるとかこんな考え方もあるということを教えていただける方(ぜひ本記事の充実にご協力ください！)
入門前に 〜ヒューリスティックコンテストって？〜
ヒューリスティックコンテストというのは、一般的なアルゴリズムコンテストと似てはいますが、以下の点が異なります。
- プログラムの出力情報、形式だけでなく、その出力結果に対するスコアの計算方法が与えられる
- ジャッジサーバは提出されたプログラムでテストケースを実行してスコアを算出する
- スコアの高さで順位が決まる
そして大概の場合、コンテスト時間はアルゴリズムよりもとても長く(1週間〜数ヶ月ということも！)、参加者はより高いスコアを求めて何度も何度もプログラムを改善していくことになります。(提出回数によるペナルティも大概ありません)
ヒューリスティックコンテストってそもそも何が楽しいの？という方には以下の記事がおすすめです。
スポーツでも短距離走とマラソンでは要求される能力が違うように、アルゴリズムコンテストとヒューリスティックコンテストでも要求される能力はちょっと違います。（共通して求められる能力があるところも似ていますね！）
問題パターンと取り組み方
概要
取り組み方
問題のパターン分けはこれからしていきますが、ほとんどの場合、以下のように分けて考えると見通しが良くなります。
- (スコアはともかく)出力条件を満たす解をまずは1つ作る(初期解と呼びます)
- スコアが高くなるように解を改善する
誤解のないように補足しておくと、先ほどヒューリスティックコンテストではコンテスト期間の中で何度も何度もプログラムを「改善」していくことになると言いましたが、「2」の「改善」はちょっと意味が違って、1つのプログラムの中で「1」で作った解のスコアを上げるように「改善」するということです。
パターン分け
では、問題をざっくりと3パターンに分けて、上記の意味合いを見ていくことにしましょう。
問題のパターンごとに解き方の方針をフローチャートにしてみましたが、そもそもそれぞれの分岐が何を意味しているのかから説明したいと思います。
「テストケースの値が全てプログラムに与えられる」とは？
テストケースの値が全てプログラムに与えられるというのは通常のアルゴリズムコンテストでは当たり前だと思うかもしれませんが、ヒューリスティックコンテストではジャッジサーバだけが知っている隠しパラメータがある場合があります。例を挙げておきます。
- 全て与えられている例
- AtCoder Ad(AHC001) Web広告を互いに重ならないように配置して満足度を最大化する問題
- 隠しパラメータがある例
- Shortest Path Queries(AHC003) グリッド上の道路網(距離不明)で、順次与えられる2点間の最短経路を出力する問題
- Project Leader(HTTF2022予選) 依存関係のあるタスクとスキル不明のメンバーが与えられ、全タスク完了の終了時間を最小化する問題
「全て与えられている例」はあまり違和感がないと思います。上のAtCoder Adでは、必要な情報は全てプログラムに与えられますが、理論上の最大値を求めようとすると計算量が大変なことになるので、なるべく高得点を目指して頑張ってね、というタイプの問題になります。
「隠しパラメータがある例」を見ていきましょう。Shortest Path Queriesでは、2点間の最短経路を求めるように問われますが、各点間の距離が一切与えられていないので、そもそも最短経路を求めること自体が不可能です。ただ、プログラムで経路を出力するとその結果がジャッジからフィードバックされるので、プログラムではその結果を元に隠された値を推定して、より適切な経路を出力することを目指していくというタイプの問題になります。Project Leaderでは、メンバーのスキルに応じてタスクを割り振っていきたいですが、メンバーのスキルが隠しパラメータになっているので、最初はうまく割り振れませんが、これもタスクを割り振るといつ終わったかがジャッジからフィードバックされるので、それを元にメンバーのスキルを推定していくことになります。
「解の一部を変更したときのスコアの再計算が容易」とは？
さて、まず「解の一部を変更」というのは何でしょう？
先ほども見たAtCoder Adで考えてみましょう。これは長方形の広告のスペースをうまく配置して満足度を最大化する問題ですが、スコアはともかくとしてひとまず問題の条件は満たしている解が1つあるとしましょう。この解の一部を変更するというのは、例えば以下のようなことを言います。
- 1つの広告枠を少し広げる
- 1つの広告枠を少し狭める
- 1つの広告枠を少しずらす
まず、この変更が可能かどうか(他の広告枠と重ならないか)についての判定が必要ですが、これは最悪でも広告枠数のオーダーで、工夫すればもう少し少ない計算量でできそうです。スコアの増減については全広告枠を考えずにその広告枠だけ考えればできそうです。この計算量の少なさのことを「容易」と表現しています。
これだけではわかりにくいので、「容易」ではなさそうな例も見てみます。
- 農場王X(RECRUIT日本橋ハーフマラソン2021〜増刊号〜) 収穫機をうまく購入・移動して、出現する野菜を収穫し、資金を最大化する問題
- Car Assembly Line(第7回Asprova) 工場ラインの各ステーションについて車種ごとに所要時間が与えられ、生産順を選んで生産台数を最大化する問題
農場王Xで解の一部を変更するというのを、例えばある日の収穫機の移動元・移動先を変える、ということにしてみます。すると、その後の日での移動がそもそもうまくいかなくなったりして解全体に影響が波及してしまいます。
Car Assembly Lineでは、解の一部の変更は例えばある2箇所の順番の車種を入れ替えるということが考えられます。これは解としては成立しますが、最終的に何台生産できるかを求めようとすると、いつどのステーションによってライン全体を止めるかということがこの変更によって大きく変化して、ほとんど全体のシミュレーションをやり直す羽目になりそうです。
「容易」か「困難」かは主観的なところもありますが、制限時間数秒程度の問題であれば目安として計算量がおおよそ2桁〜3桁前半程度以下であれば「容易」、それ以上であれば「困難」と思っておくと良いのではないでしょうか。
補足(2022/2/26追記)
MC Digital プログラミングコンテスト2022(AHC008)にて、より考察力が問われる問題が出題されました。アルゴリズムで言えばABCに対するARCやAGCのようなイメージかと思いますが、考察過程を以下の記事に書きました。興味のある方はご覧ください。
1-1. 改善重視型
テストケースの情報が全て与えられていて、かつ解の一部を変更した場合のスコア再計算が容易なパターンです。一部再掲ですが、このパターンの問題例です。
- AtCoder Ad(AHC001) Web広告を互いに重ならないように配置して満足度を最大化する問題
- Food Delivery(AHC006) 宅配注文(店＋配送先)の中から指定個数選んで、巡回経路距離を最小化する問題
アプローチ
このパターンの問題は、一度作った解を改善していくことに力を入れることで、スコアアップにつながりやすいです。よく使われる手法としては以下があります。
乱数などで解の変更する部分を決め、スコアを再計算した結果プラスになったら採用するというのが山登り法です。焼きなまし法はその発展形で、最初のうちは多少下がっても採用してみると、結果的に最終スコアが良くなることがある、という発想のものです。
コンテスト時間(プログラムの実行制限時間ではなく、参加者がプログラムを作るのに与えられている時間)が限られている場合は、まずは初期解が超単純な低スコアのものから始めて様子を見てみても良いでしょう。
さらに高スコアを目指すためのテクニック
「一部変更」の仕方を変えてみる
変更箇所は完全ランダムではなく、低スコアの箇所が高確率で選ばれるような選択の仕方をしてみるのも有効です。
また変更方法自体も、最初に考えた方法以外に何か変える方法があれば試してみるのも良いでしょう。特にビジュアライザーで結果を見たときに、何がネックになっているかがわかれば、それがうまく解消するような解の変更方法がないかを考えてみると良いでしょう。
ビジュアライザーを見て、もう少し大掛かりな仕組みを入れても良いかもしれません。AtCoder Adでは、周囲の広告が邪魔をして低満足度の広告がそれ以上改善できなくなるケースが多々発生します。このようなケースでは、低満足度の広告の隣接広告を一度リセットしてからやり直すというのも有効でしょう。
ある程度良い初期解を作る
初期解が単純でも高スコアが出る場合があるとは言え、高スコアに到達するまでの実行時間がかかりすぎてしまう場合は、ある程度スコアの高そうな初期解を作っておくという方法が考えられます。山の麓から登るのではなく、六合目まではバスで行ってしまおう、というようなことですね。Food Deliveryで言えば、予め原点に近い注文だけ集めて解を作っておくなどの考え方です。
いろいろな初期解でスタートしてみる
山登りや焼きなましをしても、すぐに頭打ちになってしまうケースもあります。制限時間内に数百万回繰り返せるのに、最初の数万回でほぼスコアが頭打ちになっているようなケースです。このような場合、到達しうるスコアが初期解に強く依存している可能性がありますので、初期解もランダムに変えてみて、数万回ずつ山登りや焼きなましをしてみて、一番高かったものを採用するというのも有効な方法でしょう。全国いろいろな都道府県から開始してみると、違う山に登れるかもしれない、というようなことです。
焼きなましのパラメータを変えてみる
焼きなまし法では、初期にどの程度のスコアの低下を許容するか、というパラメータがありますので、これを変えてみることで改善する場合があります。
1-2. 初期解重視型
テストケースの情報が全て与えられていて、かつ解の一部を変更した場合のスコア再計算が困難なパターンです。問題例を再掲します。
- 農場王X(RECRUIT日本橋ハーフマラソン2021〜増刊号〜) 収穫機をうまく購入・移動して、出現する野菜を収穫し、資金を最大化する問題
- Car Assembly Line(第7回Asprova) 工場ラインの各ステーションについて車種ごとに所要時間が与えられ、生産順を選んで生産台数を最大化する問題
アプローチ
このパターンは解を一度作ってしまうと改善が難しいので、初期解自体をなるべくスコアが高くなるように構成していくというアプローチが有効です。上の2例に共通するのは、途中まで解を作った時に、次に何を選ぶかという観点で考えられることです。いずれの場合も最終スコアは最後まで解を構成してみないとわかりませんが、途中の状態でもどういうことが「良いこと」なのかはある程度わかります。
農場王Xではn日目まで解を作ったとして、n+1日目をどうしたらより良くなるかという観点で考えることができます。この問題は、野菜を収穫したときに連続している収穫機の数に比例して点が増えるので、収穫機全体を連結にしておくというアプローチがまず有効になります。その前提で、n+1日目の行動を考えたときに、
- 収穫機が買えるときは買う(ただし最終盤では買うコストの方が高くつくのである日数や機数以降は買わない)
- 近隣に高得点の野菜があればそこに移動する
- 将来高得点の野菜が出現する方向に移動する
- 将来高得点の野菜が出現する場所に既に収穫機が置いてあればなるべく動かさない
などが良い行動と言えそうです。
Car Assembly Lineでは、n台目までの解を決めたとして、n+1台目をどうしたらより良くなるかという観点で考えることができます。この問題では、
- 各ステーションの作業者の手がなるべく空かないようにする
- かつ、ラインはなるべく止まらないようにする
- どうしても止める場合は、なるべく多くのステーションで作業遅延気味のときにしたい
などが良い行動と言えそうです。
こういったタイプの問題では、考えられる「次の一手」に対してその「良さ」を算出するような評価関数を作って解を構成していくと良いでしょう。評価関数の作り方を説明するのは難しいですが、大まかな考え方を箇条書きしておきます。
- まず「良さ」の観点を整理する（上に挙げたように、何を良いとするかの整理です）
- 目先のことだけでなく、大局的な観点も「良さ」に入れる
- 観点ごとに、良さを数値化する
- 各観点の良さの数値を適当な係数で足したり、掛けたり、割ったりして、1つの数値にする
評価関数ができたら、解を作っていくやり方には以下のようなものがあります。
貪欲法は次の一手の中で一番評価関数の高いものを選んで解を構成していく方式です。ただ、次の一手は良くても数手後にあまりよくない状況になってしまうかもしれないので、候補手を何手かずつ残しながら探索していくのがビームサーチです。
さらに高スコアを目指すためのテクニック
評価関数の工夫
テストケースによって得意不得意が出てくることがあります。不得意なケースの得点が足を引っ張って全体の得点が上がらないケースでは、不得意なケースをビジュアライザで見てみましょう。何か追加した方が良さそうな観点がないか検討し、評価関数を改善していくことがスコアアップにつながります。また、観点自体は足りていても、評価のバランスが悪いことも考えられます。このような場合は観点ごとの係数を変えてみるのも良いでしょう。
また、序盤・中盤・終盤で重視すべきものが変わる場合もあるので、フェーズごとにパラメータが変わるような仕組みを入れるのも良いでしょう。
パラメータ乱拓
評価関数を作っていると、係数や閾値などいろいろなパラメータが出てくると思います。このパラメータを変えるとスコアが上がったり下がったりすると思います。ということは、パラメータをいろいろと変更したスコアを計算してみて、1-1で見てきたような山登りや焼きなましの考え方でスコアを改善していくという手法を行うことができます。
パラメータの一部を変更した場合のスコアの再計算には時間はかかるでしょうが、解全体を数回・数十回でも作れる程度の時間があればスコアアップにつながるでしょう。
2.パラメータ推定型
テストケースの情報が一部与えられていない(隠しパラメータがある)タイプの問題です。例を再掲します。
- Shortest Path Queries(AHC003) グリッド上の道路網(距離不明)で、順次与えられる2点間の最短経路を出力する問題
- Project Leader(HTTF2022予選) 依存関係のあるタスクとスキル不明のメンバーが与えられ、全タスク完了の終了時間を最小化する問題
アプローチ
このパターンの問題は、とにもかくにも隠しパラメータを推定することが重要になってきます。フィードバックによって得られる情報を元に徐々に隠しパラメータの推定精度をあげていくことになります。典型的には以下のような方法があります。
- プログラム上に仮パラメータを持っておき、得られたフィードバックとの誤差(平均二乗誤差(MSE)等)が少なくなるように、山登りや焼きなましでパラメータを調整する
- 各パラメータを確率変数とし、何らかの分布を仮定して、フィードバックが得られるごとにベイズ更新で改善していく
- MCMC法による推定。これについては筆者自身が説明できるほど理解できていないので、AHC003の優勝者による「AHC003の2.926T解法+経緯」の記事を参照ください
難しいようであれば、フィードバックを元にした何らかの平均のような初歩的な統計手法やから始めても良いと思います。
(2021/12/11追記)
Online MST(AHC007)にて、隠しパラメータがあり、順々に隠しパラメータが明かされていくものの残っている隠しパラメータの推定の役には立たないという、推定で解くのが難しいパターンの問題が出題されました。こういったケースでは、モンテカルロ法等で各ターンの選択肢の内で有力なものを選ぶという1-2の評価値計算的なやり方の方が有効なようです。
さらに高スコアを目指すためのテクニック
序盤を工夫する
序盤は得られているフィードバックの数がまだ少ないので、当然のことながら推定の精度は低いです。精度が悪いなりに頑張って良いスコアが出るように頑張るというのも一つの方法ですが、序盤のスコアを上げるよりも推定精度を上げる方向の努力をした方が有効な場合があります。
Shortest Path Queriesであれば、ある程度わかっている中で距離が短そうな道を通るよりも、まだあまり通ったことのない道を多少遠回りでも通った方が、情報が多く得られて後々得することになります。
Project Leaderでは、メンバーのスキルがよくわからない状態で難易度の高いタスクを渡してしまって延々とそのタスクを握られてしまってボトルネックになるよりも、最序盤は少し難易度低めのタスクを渡しておくと良いかもしれません。逆にメンバーのスキルを測るために、難易度高めのタスクを渡した方が良いかもしれません。相反することを言っていますが、要は仮説を元に試してみて、良い方を選択していくと良いでしょう。
テストケース生成方法をよく読む
テストケースの生成方法をよく読むことも大切です。直接使うパラメータを生成するために、事前にいくつかのパラメータを作り、それを元に最終パラメータを生成するようなケースでは、その事前のパラメータを推定した方が良いケースも多いです。
複数パターンのパラメータを持つ
推定が難しいパラメータについては、いくつかの値を仮定して持ち、フィードバックとの誤差が少ないものを推定するという手法もあります。Shortest Path Queriesでは、Mが1のケースと2のケースで割と様相が異なります。両方のパターンを仮定してみて、フィードバックが得られたら誤差を計算し、誤差が少ない方を採用すると改善することがあります。またこの問題ではDの値が100〜2000の範囲でしたが、固定で100と1000と2000のようにいくつか用意しておいて、一番良いものを採用するという方法も有効でした。
まずは一歩踏み出そう
(2021/11/26追記)
本記事について、AtCoderの@chokudaiさんが言及してくださいました。記事内ではいろいろなアプローチ方法やアルゴリズムについて触れましたが、@chokudaiさんが仰るようにヒューリスティックコンテストとしては比較的短い4時間の大会では、そこまでいろいろ使わずとも貪欲法(1-1の改善重視型で言えば山登り法)だけでかなり戦えます。
「はじめかた」と言うにはハイレベル過ぎる気はするけど、1週間コンテスト初参加とかの人に途中で読んでもらいたいくらいの内容。
— chokudai(高橋 直大)🍆 (@chokudai) November 23, 2021
4時間？最初は貪欲だけでええんや貪欲！！！https://t.co/7AvsdHIZez
実際に、AHC006を貪欲だけで順位表2ページ目(橙perf相当！)のスコアを出せるという解説記事もあわせて紹介しておきます。
まだヒューリスティック自信がないからと恐れずに、まずは一歩を踏み出しましょう！
その他のTips
最後に、問題パターンによらない共通的な考え方や、問題そのものというよりは環境的なTipsを挙げておきます。
問題を分割する
アルゴリズムコンテストについても言えると思いますが、難しい問題は問題を分割して考えると良いでしょう。Project Leaderでは、メンバースキルを推定する問題と、タスクをメンバーに割り当てる問題に分けて考えることができます。Car Assembly Lineでは、最終的にどの車種を何台生産しようとするかを決めるパートと、生産する順番を決めるパートに分けて考えることができます。
少しずつ改善する
一気に改善しようと欲張らず、改善しそうなアイディアを1つずつ入れていって結果を見てみるというのも大事です。改善するはずだと思ったのに改善しないこともありますし、それぞれの要素が本当に改善につながっているかどうかを確かめながら進めましょう。
ビジュアライザーをよく見る
最近は公式のビジュアライザーも充実してきています。実行結果を可視化してみて、どこに改善の余地があるかを人の目で見て考えるというのはとても大切です。
ローカルテストをする
手元である程度の数のテストケース(通常は最低でも50個、できれば100個以上)を用意しておき、実行できるようにしておきましょう。ジャッジサーバに投げなくても改善効果を試すことができ、効率が上がります。
またテストケースの数を増やしておくことは、パラメータチューニングの精度向上にも役立ちます。
メモをとる
コンテストに取り組んでいる間には、すぐに実装するのは難しいけれどもこれをやったら改善するのではないかというアイディアを思いつくこともあります。そういったアイディアのストックはこまめにメモを取っておきましょう。後々やることがなくなったときはメモを見て、作戦を練り直すと良いでしょう。
また、何をやってどれだけ改善したかもメモに残しておくと良いと思います。筆者はJupyter Notebookに書き残すようにしています。
ソース管理する
アイディアを実装した結果、改善どころか悪化してしまうケースもあります。捨ててしまうのは惜しい場合、そのまま残しておくとソースコードが複雑怪奇になって、後々の改善効率に影響します。そんな対策として、Gitなどのソース管理ツールを使って履歴管理しておくのが良いでしょう。悪化したものもコミットしておき、後でいつでも戻れるようにしてから一思いに削除することで、開発効率も上がります。
コンテスト中はソース公開は通常禁止なので、くれぐれもパブリックなGitHubなどで管理しないようにだけは注意してください。
3つの改善
ヒューリスティックコンテストはいきなり高スコアの解が求まるものではありません。以下の3つの改善を意識して取り組むのが良いと思っています。
- 解の改善。これはプログラム内で解をより高スコアにしていくことで、プログラムの実行制限時間内で行っていくものです
- プログラムの改善。これはより良いアイディアをプログラムに盛り込んでいくことで、コンテスト期間内で行っていくものです
- スキルの改善。これは参加者自身のスキルをアップしていくことで、競プロ人生を通して行っていくものです
いずれの意味においても、最初はスコアが出なくても改善していけば良い話です。まずは第一歩を踏み出すことが大事だと思います。
生活を大切に
これは本当に大事だと思いますが、仕事や学業、ましてや睡眠・食事などの生活を犠牲してまで取り組まないように注意しましょう。本業や健康あってこそ、楽しく趣味に取り組むことができます。
次の一歩
良記事を置いておきます。
終わりに
冒頭にも書いたように、筆者はまだ8回しかヒューリスティックコンテストに参加していないので、全体像を分類するにはまだ早い感もあり、ベテラン勢から見るとツッコミどころも多いと思いますが、記事の改善に向けてぜひコメント等いただければと思います。または、こんな記事には任せていられないと、もっと良い記事がたくさん生まれていくことも密かに期待していることの一つです(筆者自身の勉強のためにも)。
ヒューリスティックコンテストに取り組むにあたって、少しでも本記事が参考になると幸いです。