はじめに
この記事はAtCoderで不定期に開催されているAHCにおける問題の性質別の自分の解法の選択について述べたものです。自分の場合、基本的に短期、長期のいずれも解法の大方針を変えることはほとんどなく、最初に問題をじっくり見つめて吟味したものが採用されています（短期については、二つ以上の方針を書けるほどの実装力がないことが主な理由で、長期については、時間を全投資すればそれなりの精度で吟味する時間が与えられていることが主な理由です）。ここ一年くらいはこの解法選択の直感が昔に比べて成長していると感じていて、一度今の自分の考えをまとめたいということでこの記事を書いています。先に述べたのがこの記事のモチベーションの7割くらいですが、この内容が参考になる方、より良い考えを教えてくれる方がいればと思い公開しています。
この文章では焼きなまし、ビームサーチなどの詳しい説明は行いません。「自分が取りうる解法」で解法選択において大事になりそうなイメージを述べているので、その項の内容だけで以降の内容についていけるかもしれないですし、ならないかもしれないです。すみません。
（自分が学び始めたころ、世の中の解法の記事はどれもかなり難しい印象をもっていたので、いつか、初めて○○に挑戦したい・一回○○を実装してみたけど思う結果にならなかったという方に向けた簡単な記事を書けたらと思っていますが・・・）
気を付けてはいるのですがところどころうっかり打ち間違っているかもしれません。間違いを発見されましたら優しく教えていただけるとありがたいです。
自分の考えをまとめたものであるため、以下では敬語は省略しています。
注意：以下、それなりに長いです
自分が取りうる解法
AHCでよく使う
・山登り
おなじみのやつ。暫定bestの解の一部を変えて別の解を作る。よくなってたら新しいほうの解を今のbestとして時間いっぱい繰り返す。
・焼きなまし
おなじみのやつ2。暫定bestの解の一部を変えて別の解を作る。山登りと違ってよくなくても確率で採用する。「よくない」の度合いがひどいほどで採用する確率を下げる。
・ビームサーチ
おなじみのやつ3。主に「ターン」の概念が用意できる問題において、ターンのそろっている有力セーブデータを何個かキープしておいて、各有力セーブデータでいろんなパターンで1ターンずつ進めてみる。（で、その1ターン進んだセーブデータのうち有力なものをいくつかキープ）
・モンテカルロ法
おなじみとまではいかないかもしれないやつ。有力な選択肢に対して、その選択を選んだあと最終的に（あるいは数ターン後）スコアがどうなるかをシミューレーションしてみて、最も良いものを選ぶ。（この手法はたいてい確率でどうのこうのみたいな要素があるのでシミュレーションはたくさんやってスコアの平均（たまに平均じゃないこともある）をとる）
・貪欲+破壊再構築（山登りの一種）
なんかのルールで貪欲に解を決める。そこから一部を破壊（設置系の問題なら「一部のアイテムを取り除く」、ルートを決める問題なら「一部のルートを未定にする」など）して、破壊した部分を貪欲で決めなおす。よくなってたら採用。
もちろん、問題の全体の方針として使うこともあれば、問題の一部に注目してその部分を解くのに使うこともある。
AHCではあんま使ってない
・MCTS
自分は今のところ有効に使えてないので略。
・機械学習
これはコンテストによっては主方針として十分強力なこともありそうだが、なんの知見を持っていないので「なんかこの問題機械学習が使えそうだな～」といいつつ実際に使えるかどうか全然わからない。ので略。
問題の性質と向き不向き
この項を読む方へ
ここでは問題が持つ諸性質について、山登り、焼きなまし、ビームサーチ、モンテカルロ法が向いているかどうかの感覚が述べられている。もっとも重要なこととして、「執筆当時の私が思う」向き不向きで、各解法について、人それぞれにまた違う印象を持ちうることに注意されたい。すべてに「～と今の私は思っている」と続いていると考えてほしい。
上で述べた4つの解法（山登り、焼きなまし、ビームサーチ、モンテカルロ法）について、向き不向きを+3~-3で評価し、各見出しに(-1,+3,-2, 0)などと解法順に表記する。評価方法にはブレがあるが、おおよそ以下の通り。
・+3 この性質があると非常に扱いやすくなる / この性質がないと致命的に扱いにくい
・+2 この性質があるとまあまあ扱いやすくなる / この性質がないとまあまあ扱いにくい
・+1 この性質はないよりはあったほうが良い / たいていはプラスに働く気がする
・ 0 プラス要素とマイナス要素がありどちらともいえない / この性質はこの解法に影響を及ぼさない
・-1 この性質はあるよりはないほうが良い / たいていはマイナスに働く気がする
・-2 この性質があるとまあまあ扱いにくくなる / この性質がなければとまあまあ扱いやすい
・-3 この性質があると致命的に扱いにくい / この性質がないと非常に扱いやすい
・-- 自分の中での感覚が定まっていない /わからない
考える問題は各性質をもってたりもってなかったりするので、その総合評価で主解法を決定している。部分的な問題に区切れば別解法が使えたりもするのでそれも検討する。
最後の総合評価は自分の特性（各解法の実装経験量など）で多少ゆがめている気がする。（執筆時の自分の場合、焼きなましは定数倍高速化がうまくできておらず、ビームサーチもまた状態コピーなどのコストをカットできていないため、山登りが少し選ばれやすいように思う。山登りからなら焼きなましに切り替えられることもあるし・・。）
重要性質
なんとなくここは各解法が欲している基本的な性質を書いている。問題がこの性質を含んでいるか？というよりはこの性質を持つ（あるいは持たない）ような問題の見方ができるか？というのを考えるほうが多いかもしれない。
問題にランダム要素が含まれる(-3,-3,-3,+3)
問題に乱数を使ったランダム要素・不確定要素があり、その要素の効果が表れる直前まで乱数の結果を知らされない場合。カードゲームのドローがこの代表的なものにあたる。これはモンテカルロ法についてはほぼ必須といってよい条件で、不確定要素のないような問題ではモンテカルロ法は他3つの劣化版となってしまうのがオチ。ランダム要素がないならモンテカルロ法はいったん忘れてもよい。逆にランダム要素がある場合、焼きなまし、ビームサーチが用いられるのは例外を述べたほうが早い。
例外というのは、
・不確定要素の数値的な影響があまりに小さい
（「あるカードを引いたらスコアに0.001点加点する」みたいな）
・確率分布などの統計量を見ることで不確定要素の効果が十分見積もれる場合
（ただ、例えばカードゲームの場合はこのターンで各カードを引く確率が計算できても、「その後このカードを使うとこの特殊効果が発動して次のドローは2枚になって・・・」など、最終的なスコアへの寄与は極めて難解であることが多い）
・たくさんのサンプル（パラレルワールド的なやつ）を持っておくことでごまかせる場合
などである。なお、すでに確定している部分と矛盾しない乱数結果を考えるのが難しい場合は、モンテカルロ法も難しい。
解の一部を変えて新しい解を作ることができる(+3,+3,+1, 0)
説明：このプロセスは山登り・焼きなましにおいて不可欠なもの。以下説明では遷移と呼ぶこともある。
ビームサーチにおいては、この性質があれば状態をコピーしなくてよいパターンになる可能性がある。（結局その実装の経験はない）
例：「5桁の数字」という条件でなるべく大きな数字を求めるような問題。
46378という解に対して、「ある桁の数字を変える」という操作で43378, 56378などの新しい解を作ることができる。
遷移が細かい(+1,+2, 0, 0)
説明：この遷移が解のごく一部を変えるようなものである場合。これは焼きなましによっていい感じの解へと流れていきやすい。山登りにおいてもうれしいものの、山登りは局所解を求める特性上遷移が大きくてもあまり問題にならない印象がある。
遷移の計算が高速(+2,+3,+1, 0)
説明：山登りに比べて焼きなましは悪くなる変化も採用するという仕様の都合で、考える規模と比べて十分に高速なら焼きなまし、そうでないなら山登りに軍配が上がる。同解法焼きなましバトルでは遷移の計算量が異なるとほぼ確実に敗北なので、定数倍高速化の差くらいには押さえておきたいところ。（というくらいに影響度が高い）
遷移の「逆遷移」が用意できる( +1,+2,+1, 0)
説明：これは盲点だったが、逆遷移のない焼きなまし場合、焼きなましの性能が保証できない。例えば「整数」という条件で数字を最小化するような問題を考える。極端だが遷移として「数字を+0~+6する」とすると、いくら遷移を繰り返しても確率での採用があるたび数字が大きくなってしまう。山登りでは、ある遷移が採用されたらたいてい逆遷移は採用されないのでここまで大きな問題にはならないが、評価値が変わらないものを採用するかによっては大きく影響を受ける。
ビームサーチにおいては、この性質があれば状態をコピーしなくてよいパターンになる可能性が高まる。
今の例題では逆遷移が用意できて、遷移を「数字を-6~+6する」とすると、期待の結果になる。BがAに近い⇔AがBに近いみたいな「距離」の拡張の気持ちで考えるといいのかも。
遷移を繰り返し採用すれば好きな解から好きな解へ移動できる( 0, +1, 0, 0)
説明：盲点2。この性質があるなら、焼きなましは時間をかけることで最適解を見つけられるのでこの性質がプラスにはたらく。問題の規模が大きかったり、到達できる解のうちに十分最適解に近い値が出せるものがあるならあんまり気にしなくてよかったりする。山登りでは結局局所解で止まるのでその部分が効くことは少ない。
例：「5桁の数字」の例では、5回遷移を繰り返すことで数字を好きな数字に変えることができる。
解を構成している途中段階が書けて、その途中段階に評価を与えることができる( 0,+1,+3,+2)
説明：解ではないが、解の作りかけのような状態が作れる場合。ビームサーチにおいては、この作りかけの状態の評価が不可欠。解の作りかけ自体は発想次第で無理やり作れるが、その途中段階に評価（最終結果の妥当な見積もり）が与えられるかが肝。モンテカルロ法においては、シミュレーションを最後までやらずに評価を与えられるので良い結果が期待できる。焼きなましにおいても、この途中段階を利用することで一時的にValidでない解に遷移できることがある。
例：レースゲームの運転を考える。最速で一周回ることを目的とすると、途中まで走っている状態で、経過時間と残り距離からおおよそ妥当な評価を与えることができる。
途中段階の「段階」を数値化することができる( 0, 0,+2,+1)
説明：ビームサーチは各有力候補の進み具合は揃えられたほうが圧倒的に良い。進んでるものと進んでないものを比べるのは評価の公平性を失う可能性がある。すべてを見通した「神の評価」があるなら気にしなくてよい。あるいは十分それに近い評価があるならごまかせるかもしれない。この数値化は整数であって1ずつ上がるもので最大値があまり大きすぎないものがうれしい。
例：レースゲームにおけるチェックポイント通過数.は進み具合を示す指標になる。
途中段階の「段階」を進めるような操作が書ける( 0, 0,+3,+1)
説明：ビームサーチで「1ターン進める」というのはこの操作のこと。これがないとビームサーチはできない。なお、その操作がコードで書ける（かつそんなに計算が重くない）というのは大事。
例：レースゲームにおいて「次のチェックポイントまで進む」という操作は段階を進めているといえる。段階を1だけ進める必要はなく、いくつか段階を飛ばすものも一応対応可能。「しばらくここで止まる」という操作も試したいようなら、時間など何らかの別の指標が欲しい。
主な性質にかかわってくる性質
解の要素がくっついている(-2,-2, -1, 0)
説明：Validな解の条件に解の要素同士をくっつけるような要素がある状態。Validな解を作るために他の要素を考慮しなければならず、山登り・焼きなましにおいては一要素だけを変更するような遷移が難しい場合がある（焼きなましにおいては一時的にValidでない解を許すという回避策がある）。この性質は問題自体を難しくさせているので、どの解法でもある程度困ることではあるが、ビームサーチは評価時の見積もりにうまく組み込める可能性があるので比較的その影響が少ないと思う。
例：「5桁の数字」という条件に「各桁の数字は(隣の桁の数字-1)か(隣の桁の数字+1)」という条件を追加した状態で、なるべく大きな数字を考える（最適解は98989である）。98765という解から一桁だけ変えて新しい解を作ろうとした場合、制約から8,7,6の部分を変えることはできず、かなり動かしづらい印象を受ける。また、この遷移では最適解に到達できるとは限らず、89898から98989へは何度遷移を繰り返しても到達できなかったりする。
解の要素に順序関係がある( 0, 0,+1, 0)
説明：問題が何かの順番を出力ものである場合。この性質単体ならあまり気になるものではなく、ビームサーチが手を付けやすいかもしれない程度。後述のより進んだ性質がいろいろ悪さしてくることがあるので注意。
例：「5桁の数字」でなるべく大きな数字を答える問題を考える。これを5個の数字を並べる問題ととらえると、桁は場所に意味があるので順序関係がある。
積み木ものせる順番を考えると順序関係になっている。
順序が異なると制約を満たさない(-2,-3, 0, 0)
説明：順番に依存した制約条件が課せられている場合は、「順番を入れ替える」というような単純な遷移が書きにくくなることで焼きなましが難しくなる。山登りは比較的大きな遷移を採用できるのでまだ影響は小さい。これは程度問題で、致命的にならないこともある。
例：積み木は、のせる順番が変わるとのらないことがある。積み木のセットによっては「三角の山の上に四角」など無茶なものばかりになる可能性もある。
グリッド上での移動方向列（→↑→↓→）なども、入れ替えると盤内の障害物に当たったりする。迷路のように入り組んでいなければ、入れ替えが成功することも多い。
前で述べた「5桁の数字」問題は、順序関係に関連した制約がないのでそういった心配はない。
順序が異なると結果が大きく異なる( 0, 0,+1, 0)
説明：二つの順番が逆になるだけで結果が大きく異なる場合。この場合はビームサーチで「順番が違うけど結果的に似たような状態」というのが発生しにくく、有力候補がすべて似た状態になることを自然に防ぐことができる。たまにそれがプラスにつながらないこともあるが、おおむねプラスに働く。順序が異なるが同じ・似た状態になることが多い場合は、それらを間引くような作業が必要になる。（でなくても間引く操作はたいてい行ったほうがよいが）
例：コマンドバトルRPGにおける「力をためる技と必殺技」など。こういう要素が多いほうがバラバラになりやすい。「7ダメージを与える技と20ダメージを与える技」のようなものは入れ替えてもあまり変わらないので対策が必要。
過去のAHCで確認
過去のAHCの問題について性質を見て解法を見直していく。
※途中で何をまとめているか自分でもわからなくなってしまったので書きかけで没になりました
どうしても見たい場合はこちら
自分が参加していたコンテスト
AHC014
既存の3点に1点を加えて長方形を作る問題。強い特徴として
・順序関係、それに対する強力な制約の存在
・順序入れ替えが可能でもスコア変化なし
・任意の途中段階に対して最終結果を見積もることは難しい
・ビームサーチで揃えたい「段階」の数値化が難しい
となり、否定的に山登り・焼きなましが良いと思われる。当時の自分は新参者で、貪欲＋乱数で時間いっぱいやり直している（全破壊山登り）。
今なら部分破壊山登りかなあ。高速化しても焼ける段階までは見えてこないのだが当時の最上位陣はみんな焼いているらしい。改めてすごいな・・・。
部分破壊山登りは局所解にすぐはまりそうな構造ではあるので、焼いたほうがよくなるラインが比較的低いのかもしれない。
AHC016
今回の枠組みで考察するの難しそうな変わり種。グラフを過去に送る問題で、頂点番号情報がなくなることと、各辺一定確率で辺情報が反転するという問題。
・辺の有無が反転するときに乱数要素があるものの、正規分布を用いて発生数は見積もることができる。
・解自体は無茶苦茶少ない（元はどのグラフかを高々100通りから選ぶ）
という形なので、エラーが起こる前の候補について、何とかもっともらしさを見積もることができれば、そのもっともらしさが一番高いものを答える貪欲しかなさそう。煩雑な数式を正しく変形できる気力があるかが一つの壁になっていそう。
候補は自分で用意できるので、互いに大きく異なるグラフを選びたいが、当時の自分はクリークを思いつけなかった。
AHC018
硬さの異なるフィールドで、地面を掘って水道をつなげる問題。
問題のサイズがでかくてそのまま二次元配列を用意したくないし、近くのマスの硬さは近いという感じだったので、問題を小さい問題に圧縮。期待値的な最適行動はもう得られないだろうが、問題自体が難しいので許容していいと思う。
ランダム生成の硬さはそのマスを掘りきるまではっきりしないので、乱数要素は強め。これまでの結果に矛盾しないフィールドの生成が難しいため、モンテカルロ的なシミュレーションで解決はしなさそう。→ある種貪欲でいいんじゃないか？
AHC023
今やっても多分苦手な問題。不思議な形をした畑に作物を植える問題。作物も多いし問題の規模的に貪欲だったりDPだったりで決めるしかないんじゃないか？→いろいろそぎ落として本質だけになった最上位陣のものを見るとなんか焼けそうな情報量になってた。すごい。遷移も評価も想像以上に高速に動いてるみたいだし、データの持ち方やアルゴリズム次第で「うまくいきそう」の判定ラインが大きく変わるなあ。
AHC025
重さを知らないアイテムたちを天秤を使って何等分かにする。
乱数・インタラクティブの要素があるので全体を焼いたりビーム打ったりは無理である。これまでの結果に矛盾しない重さを確立を踏まえて生成するのが簡単ではないので、モンテカルロも難しい。これが簡単に生成できたらモンテカルロが最有力の可能性もあった。
各回ごとに天秤の使い方を決定するという問題として考えると、重さの予想がある程度つけば効率的な使い方を焼く・山登りするというのが有力か。
一番困るのが「効率的な使い方」の意味で、この問題はそれぞれの重さを特定していくのが良いとは限らなかったんだよなあ・・・。（特にクエリ数が足りない場合）
