焼きなまし法が使えなくても AHC 橙になれたよ

AHC レーティング橙になりました！

AtCoder のヒューリスティックレーティングが橙（2400+）になりました。

ヒュ橙になりました！
-----
Kiri8128さんのトヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）での成績：4位
パフォーマンス：3001相当
レーティング：2327→2483 (+156) :)
Highestを更新し、三段になりました！#AtCoder https://t.co/c58YeqW7rw pic.twitter.com/LtXniT9chn
— きり (@kiri8128) November 5, 2023

（参考：アルゴ橙記事）

kiri8128.hatenablog.com

AHC で橙になるまでにやったこと

AHC に出る

言語

基本 Python（PyPy）でやってました。 1 回だけ Rust で書き換えたことがあります（AHC 014）。

得意問題・苦手問題

同じレート帯の中では、基本的に高速化や探索ゲーは苦手で、評価関数や貪欲系が得意だと思っています。AHC と言えば焼きなまし法やビームサーチ等の最適化アルゴリズムを使う印象がある人が多いかもしれませんが、私は AHC でこれらをうまく使えたことはほとんどありません。逆に言えば、焼きなまし法が使えなくても橙ぐらいまでは十分狙えるということが示せたと思います。

【得意】

評価関数ゲー
貪欲ゲー
戦略ゲー

【中間】

盤面構築ゲー
推定系

【苦手】

焼きなまし
ビームサーチ

問題形式としてはインタラクティブのものに得意意識がありました。ただ入橙したときの AHC 026 が短期かつ非インタラクティブで大当たりを引いた影響が大きく、プロットしてみるとむしろ非インタラクティブ寄りにいるみたいです。

あの、カテゴライズをミスっていたので修正しました（ごめんなさいー🙇）

「RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜」を非インタラクティブに変更したので、これに出ていた人は下方向に動いているはずです pic.twitter.com/mWwzmQtomb
— きり (@kiri8128) December 1, 2023

ところで私は Long & Interactive で稼いでるつもりだったんだけど、この前の AHC 026 （Short & Non-Interactive）で大当たりを引いたのでむしろ中央下ぐらいに来てます
— きり (@kiri8128) November 23, 2023

プロット方法について

なおプロットに用いた計算方式の概要は次のとおりです。

コンテスタント（参加者） $c$ およびコンテストいくつかからなる集合 $S$ について $f_c(S)$ を、過去に $S$ に含まれるコンテストのみに出ていたとした場合の $c$ の Rating とする
長期コンテストの集合を $S_{long}$ などする
、をベースにして、次のつの調整をした位置にの ID をプロットする
- レートが高いほど影響を強くする（一色で $1.08$ 倍）
- プロットが一部分に集中しすぎないように単調増加な奇関数で調整
文字の大きさはレート依存（ $1600$ 以上は一色で $1.5$ 倍、 $1600$ 以下は $3$ 色で $1.5$ 倍）
ただし文字数による調整あり

使ったコンテストはこれまでの Rated コンテストです。カテゴリは下記のとおり設定しています *1 。

コンテスト	問題	長期 or 短期	回答形式
AHC001	AtCoder Ad	長期	非インタラクティブ
AHC002	Walking on Tiles	短期	非インタラクティブ
AHC003	Shortest Path Queries	長期	インタラクティブ
AHC004	Alien's Genome Assembly	短期	非インタラクティブ
AHC005	Patrolling	短期	非インタラクティブ
RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜	農場王X	長期	非インタラクティブ
HACK TO THE FUTURE 2022 予選	Project Leader	長期	インタラクティブ
AHC006（京セラプログラミングコンテスト）	Food Delivery	短期	非インタラクティブ
AHC007（THIRD プログラミングコンテスト 2021）	Online MST	短期	インタラクティブ
AHC008	Territory	長期	インタラクティブ
AHC009（モノグサプログラミングコンテスト2022）	Robust Memory of Commuting Routes	短期	非インタラクティブ
AHC010（ALGO ARTIS プログラミングコンテスト2022）	Loop Lines	短期	非インタラクティブ
AHC011	Sliding Tree Puzzle	長期	非インタラクティブ
AHC012	AtCoder 10th Anniversary	短期	非インタラクティブ
AHC013（RECRUIT 日本橋ハーフマラソン 2022夏）	Server Room	長期	非インタラクティブ
AHC014（estie プログラミングコンテスト2022）	RectJoin	長期	非インタラクティブ
AHC015（トヨタ自動車プログラミングコンテスト2022）	Halloween Candy	短期	インタラクティブ
AHC016（HACK TO THE FUTURE 2023 予選）	Graphorean	長期	インタラクティブ
AHC017（THIRD プログラミングコンテスト 2022）	Road Repair	長期	非インタラクティブ
AHC018（RECRUIT 日本橋ハーフマラソン 2023冬）	Excavation	長期	インタラクティブ
AHC019（MC Digital プログラミングコンテスト2023）	Silhouette Block Puzzle Creation	長期	非インタラクティブ
AHC020（ALGO ARTIS プログラミングコンテスト2023）	Broadcasting	短期	非インタラクティブ
AHC021（TOYOTA Programming Contest 2023 Summer）	Pyramid Sorting	短期	非インタラクティブ
AHC022（RECRUIT 日本橋ハーフマラソン 2023夏）	Exploring Another Space	長期	インタラクティブ
TOYOTA Programming Contest 2023 Summer final	Transit Warehouse	短期	インタラクティブ
AHC023（第10回 Asprova プログラミングコンテスト）	Crops on Grid	長期	非インタラクティブ
AHC024（丸紅プログラミングコンテスト2023）	Topological Map	短期	非インタラクティブ
AHC025	Balancing by Balance	長期	インタラクティブ
AHC026（トヨタ自動車プログラミングコンテスト2023#6）	Stack of Boxes	短期	非インタラクティブ
AHC027（HACK TO THE FUTURE 2024）	Recurring Cleaning Route	長期	非インタラクティブ
AHC029（RECRUIT 日本橋ハーフマラソン 2024冬）	Business Simulation Game	長期	インタラクティブ
AHC028（ALGO ARTIS プログラミングコンテスト2023 冬）	Lucky Words	短期	非インタラクティブ
AHC030（THIRD プログラミングコンテスト2023）	Polyomino Mining	長期	インタラクティブ

成功回の傾向と戦略

これまでの参加で順位が良かった回（Rated 50 位以内）の戦略です。表を見ると、評価関数や貪欲で稼いでいることが分かります。

順位	コンテスト	問題	解法概要	解法リンク
【番外編】Unrated 2 位	新ジャッジテストコンテスト -Heuristic-	AtCoder Contest Scheduling (Online Version)	謎の評価関数に基づく貪欲	リンク
4 位	AHC 026 （トヨタ自動車プログラミングコンテスト2023#6）	Stack of Boxes	貪欲	リンク
13 位	AHC 018（RECRUIT 日本橋ハーフマラソン 2023冬）	Excavation	評価関数と戦略	リンク
26 位	AHC 025	Balancing by Balance	戦略	リンク
27 位	AHC 021（TOYOTA Programming Contest 2023 Summer）	Pyramid Sorting	評価関数に基づく貪欲	リンク
36 位	RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜	農場王X	評価関数と戦略	リンク
38 位	AHC 008（MC Digital プログラミングコンテスト2022）	Territory	盤面構築＋戦略	リンク

評価関数・貪欲の考え方

評価関数・貪欲ゲーのときに高順位になることがあり、評価関数をどうやって作っているかなど聞かれることがあります。

貪欲とか評価関数の思いつき方聞きたいかもしれないです。言語化できる類のものでもないのかもですが、、
— ぱらぼろ (@r3yohei) November 26, 2023

きりさんみたいな天才貪欲が書けなくて困っています……今度天才になる方法を教えてください！
— TERRY (@terry_u16) November 6, 2023

「天才貪欲」「天才評価関数」のような呼ばれ方をすることもありますが、天から降って来る訳ではなく、また何も考えずに作ったらたまたま当たるという訳でもなく、ある程度根拠のある（数値化できる）指標や簡素化した状況での理論値をもとにアレンジして作るというのが基本だと思っています。

以下で自分なりの考え方や普段考えていることを書きます。なお、今後のコンテストでも広く使えるようにしたいので、なるべく汎用的・抽象的な記載にしています *2 。

具体的な使用例があるものは後述します。

問題を簡素化する
- AHC の問題は厳密解が計算できないように適度に複雑になっていますが、なんらかの簡素化を行うことで状況をつかみやすくします
- 簡素化というのは、問題の本質を失わない範囲で情報を捨てるなどにより簡単にすることです。例えば「取得・計算できうる情報のうち、『ある部分』について計算コストがとても大きいが、そこを無視しても結果に 10% 程度しか影響しない」などが分かれば、その部分を捨てることで、考察を簡単にしたり計算の実行時間の節約につなげたりすることことができます
- なんでも切り捨てればよい訳ではなく、考察・計算のコストが高い割に最終結果にほとんど影響しない部分を捨てるのが大事です
寄与の概算
- いくつかの簡素化前提をおくことで、その前提の下での理論値を計算できたり、各種指標に対する寄与を直接計算できるようになったりことがあります
- 仮に最終スコアに対する寄与が計算できれば、それが最大になるものを選ぶとそれっぽい貪欲になります
どうなると嬉しいかを理解する
- 嬉しさを数値化をしておくと便利です
- この嬉しさは、直接何らかの寄与になっていなくても、大小比較のための順序を決めるためだけの情報でも OK です
- 複数の嬉しさを合算する場合は、係数を吟味する必要があります
- 例えば $A$ も $B$ も大きい方が良いなら単純に $A+B$ を指標にする手もあるかもしれませんが、 $A$ が $1$ 増えることが $B$ が $10$ 増えるぐらいの効果がありそうなら $10A+B$ を指標にするのが良いですね。
評価関数の設定
- 行動を決定するタイプの問題では、各行動に評価を定めることで評価関数ゲーに落とし込むことができます
- 最終スコアに対する寄与でなくても、「嬉しさ」を基準とした評価関数でも OK です
- 複数の指標がある場合もすべて評価関数に合計すれば良いですが、優先度の高いものの影響が大きくなるように調整します（嬉しさの項と同様）
- 不確実性による評価の補正が有効な場合も多いです（すぐに実現できるものは確実性が高いが、将来実現できる予定のものは状況によって変わる可能性があるので適当に割り引くなど調整する）
- ターゲットを定めることも有効です（ $1$ ターンで○点ぐらいは欲しい、最適解だと△点ぐらい取っているはずだ、など）
ステップを分解する戦略
- 特にターン制の問題では、まず序盤で○○という状況にする→その後△△を行う、という複数ステップでの攻略が有効になることがあります
- 「○○なら△△が計算できるのに・・」「□□という状況ならあとは貪欲でできるのに・・」のような願望があるときに、現実的なコストをかけることで実現できるなら試してみるのもありかもしれません
解法選択時の概算
- 解法・アイデアが浮かんだとしても、結果的に外れ方針になることもあります
- 実装に走る前にその方法でどれぐらいのスコア・順位が見込めるかを概算することで、外れ方針に突っ走ってしまうリスクを減らせます *3
- あるいは逆に、上位陣のスコアや目標スコアをもとに、どれぐらいの改善が求められるのかを想定しながら解法を考えることが有効になることもあります
- 例えば $1$ ターンのコストを平均 $10$ に抑えたい場合、ターンごとに $8$ のコストを掛ける処理は相当なベネフィットがないと使えないが、平均 $0.5$ 程度のコストであればガンガン使って良さそう、など。コストとリターンの両方が数値化できるとなお良いです。
パラメータの設定
- 上位陣では、手元でたくさん回すことでチューニングしているのを見かけますが、私はあまりやっていません（できていません）
- 基本的に、パラメータは最初はなんらかの概算を行って最適そうなものを選びます
- コンテスト終盤になったらいくつかのパターンを比較することも検討しますが、当初の予定と大きくずれることはあまりないです
- 序盤でチューニングしすぎるとメタ局所最適に陥る可能性があります。
平均と分散
- たくさんの入力変数や乱数がある場合、個々の平均と分散（および独立でない場合は共分散）が分かればそれらの合計の分布の平均と分散が分かります
- 変数の推定の際、平均と分散が分かれば十分なことも多いので、分布が複雑な場合などでもまずは平均・分散を調べるのは有効です
- 理論値が計算できなくても、入力データを乱数から作成することで、平均・分散の予測をすることもできます
入力の分布
- AHC では、入力の制約だけでなく、入力の生成方法（確率分布）が与えられます *4 。
- 回によっては「必ずしも理解しなくても良い」のような文言があることもありますが、これはワナです。必ず熟読して理解しましょう。
- 各パラメータがどのような値を取り得るかを理解することで、その後の各種概算が可能になります。
- 場合によっては、いろいろな指標の理論値（平均・分散など）が計算により求まることもあります。

イメージが付きづらいものもあるかもしれないので、次節でうまくいった例を挙げてみます。

うまくいった例

寄与と嬉しさ、ターゲット

寄与と嬉しさを考えてうまくいった例としては、（上でもでてきた）新ジャッジテストコンテスト Heuristic があります。こんな感じで考えてました。

「上振れ」は上述の「ターゲットを定める」に近い考え方です。

【考え方】

Cost はその日だけみると c_i * (d - last_i) だけど、まだ同じぐらい続くと考えると (d - last_i) を 2 乗したいが、それはやりすぎなので 1.8 乗にした。
Benefit は s_i としたいが、上振れを選びたいので、上振れからの差を足す感じで。 σ だと大きそうだったから 0.8σ にした。
— きり (@kiri8128) August 6, 2023

複数ターンで達成できる効果

複数ターン等を使ってある状況を得るような場合は、 1 ターンあたりなどのコストに置き換えると公平に評価できます。例えば農場王X では、連結を保っているマスの集合から $k$ マス離れたところに評価が $s$ であるマスがあれば、 $\displaystyle\frac{s}{k}$ などと評価できます。ただしあまり遠い場合は不確実性が増える（そこまで行くまでに他の有力候補が出てくるなど）ので、適宜割り引く方法もあります。もし厳密解を求めたいなら他のすべての選択肢を考慮して今やろうとしている方法に勝つのがあるかを計算する必要がありますが、それだと計算量が爆発しますよね。ヒューリスティックではあまりに複雑なところは確率処理することで簡素化できます。

・収穫機は 50 個まで買う

（マスの評価値）
将来そのマスから得られる金額の割引現在価値
割引率は移動先が 10% 、消す方が 5%

（周辺補正）
マスの近隣（そのマスからの距離が d ≦ 3 かつほかのマスからの距離が d より大きいマス）の評価値を考慮
— きり (@kiri8128) September 12, 2021

解法の概算

解法の概算が役に立った例としては、 AHC 026 があります。本問の戦略としては、

各列をソートする
列ごとに近い数を集める（例えば 0～19 は左端の列に置くなど）

などが考えられます。 1. では、ひとつずつ出す・戻すをすると一回のコストは $2$ なので、列ごとに $40$ 、合計 $800$ のコストがかかりスコア $9200$ 点ぐらいが狙えそうです。複数同時移動も許すと、確率 $\displaystyle\frac{1}{2}$ でくっ付けられると考えると一回のコストは $1.5$ 程度に抑えられるので、特に工夫しなくてもスコア $9400$ は出せそうと予測することができます。

一方、 2. の方法では、例えば

一旦すべて右端の列に集める（コスト $21\times 9=189$ ）
上から見て列 1～9 に分解する（コスト約 $2 \times 200=400$ ）
小さいやつの列から見て順に回収する（コスト $2\times 200=400$ 弱ぐらい）

という方法がありますが、これだとスコア $9100$ も達成が難しそうです。

実はコンテストの序盤（30 分～ 1 時間ぐらい？）で、一瞬 2. の方法を検討していたんですが、順位表を見たら既に $9300$ 程度の人がいたのですぐに棄却して再考したところ 1. を思い付くことができました。

#AHC026 おつでした。
1,415,168 点で 4 位でした。

やったことの概要：
・各列をソートすれば上から取れるので、ソートすることを考える
・9 個の余剰スペースが使えるので、降順になっている塊ごとに適当な列に置いて、大きい方から戻す
— きり (@kiri8128) November 5, 2023

影響による優先度付け

概算ではなく実験によって効果が小さそうだったから無視した例もあります。下記はハーフマラソン2021 のコメントです。

序盤は 200 回ぐらいパスしてもほとんど変わらなかったからいろいろサボった
— きり (@kiri8128) September 12, 2021

ステップに分解する戦略

「ステップ分解」は AHC 026 （ソートしてから出す）、 AHC 025 （グループソートしてからチャレンジする）、 AHC 008 （まず犬トラップをして、その後は壁を配置してから仕留めに行く）などで使えました

簡素化前提による理論値計算

AHC 018 解法の最後のところで一段階の攻撃力を $\sqrt{\displaystyle\frac{2hC}{k}}$ にするところなどでは、問題を簡単にして相加平均・相乗平均の関係から（簡素化前提での）理論値を求めて使いました。

その他工夫など

その他、 AHC コンテスト中に考えていることや工夫などを列挙しています。

盤面の設定
- テストケースによらず強い盤面が存在するときは、事前に盤面を決めて固定する（AHC 008 など）
拡張性の高いコード
- 最初のアイデアだけでなく、将来的に使うであろうアイデアを考えて拡張しやすい設計にしておく
- 最初は使わない機能でも枠だけ作っておいて自明設定にしておく（あとで必要があれば書き換える）など
- 終盤に局所的に良いアイデアを思いついたとき、設計が窮屈だと実装が大変すぎて断念してしまうことになるともったいない
戦略の工夫
- 自由度と扱いやすさのトレードオフ
  - AHC 018 では、ルートを必ず 10 マス刻みの格子を通るという制約を付けることで、自由度を犠牲にしながら実装・考察を簡素化する選択をした
- コンピュータに任せる探索と簡素化前提に基づく理論値計算の最適化の併用
  - AHC 016 では、ある前提に基づく理論値を計算することで計算量を改善した。ただし記事にも書いたように結果的にはうまくいかなかった点もある
実行速度と実装速度のトレードオフ
- まずは動くことが大事なので、実行速度は遅くても実装しきるのが大事
- ただし後から部分的に改善できるように、どの部分でサボっているかを理解しておくのと、後から修正しやすい設計にしておくとよい
デバッグの工夫
- 提出コード、手元実行コード（1 ケースのみ）、手元実行コード（複数ケースで得点確認）、コードテスト、などを同じコードで実行できるようにしておく
- 手元実行コード（1 ケースのみ）では、デバッグ用の出力を無限に吐き出して、意図通り動いているかをチェックする
- 実行時間が大事な場合は、実行時間を処理ごとに計測して何がボトルネックになっているか検証できるようにする
設計と実装の役割分担
- 特に長期だと設計をちゃんと作らず実装を始めると混乱してやっぱりやめるみたいなことになりがち
- 設計を作る人と実装を作る人を分けるとお互いに自分の役割に専念できて良い
- ただし AHC では複数人参加が認められていないので、長期コンなら例えば「昼の自分が設計書を書いて夜の自分に実装を依頼する」→「夜の自分は依頼を見て、期日（翌朝）までに納品する」みたいにやるとよい
手元の実行速度とジャッジの実行速度の差
- 手元では PyPy 環境を構築していないので、ジャッジに比べて 5～10 倍ぐらいの時間がかかることが多い
- コードテストでループ数を計測して、何倍の時間回せば同じ条件になるか調べておく
得点・改善量の見積もり
- 実装しようとしている解法で何点取れるのかを事前に見積もる
- 局所的な改善では、改善量があまりに小さいと実装時間をかけたくないことがある
- 改善量をある程度見積って効率（≒予測改善量÷実装時間）の良いものを優先する

良くならないはあるあるですね。今回は影響が見積りやすいものが多かった（ソートする列の一番下が最初から最大になっているのは全体で 1 箇所弱ぐらいとか、列内で隣り合うべきものが元から隣り合っているのは 10 箇所ぐらいありそうとか）ので比較的やりやすかった気がします
— きり (@kiri8128) November 14, 2023

ビジュアライザの活用
- ある程度のものが作れたら、そこからの改善はアイデアや微調整が多くなる
- そうなるとビジュアライザが有効。具体的には次のような感じ。
  - ビジュアライザをステップごとに実行して、「このターンではこっちの方が良いのでは？」というのを見つける
  - 単にビジュアライザの動きを見ているだけではなぜそう判断したのか分からないので、適宜コメントや手元実行のデバッグコメントを見てなぜそう行動したかを確認する
  - ロジックに改善点できるがあれば、それを抽象化して設計に落とし込み実装する
  - 修正前に比べて良くなったか検証する
- ビジュアライザは自動実行ではなく、 1 ステップごとに見るのが良い（必ずしも全ステップ見る必要はなく、大きな動きをするところだけでも良いかも）
入力パラメータによる場合分け
- 特に長期コンでは、入力パラメータごとに最適な戦略が異なる場合が多い
- 極端な例でのスコアを確認したり、ビジュアライザを回してみたりしてどういうケースで弱いのかを把握する

FAQ

Q: 焼きなましを使わないのはなんで？

A: 敢えて使ってないんじゃなくて、使おうとしたこともあるけど結果的に順位に反映されていない感じです。例えば AHC 024 も焼きなましを実装する予定だったけど本番中間に合わなかった感じ。

昨日のやつバグってちゃんと焼けてなかったので修正したやつ

Seed 0 2223 点#AHC024 pic.twitter.com/gsSbTBoqAZ
— きり (@kiri8128) September 25, 2023

Q: ヒューリスティックでも Python しか使わないのなんで？

A: まだ環境構築などの準備と言語の習得が整っていないので使えていないです。幸い、私が得意な貪欲ゲーや評価関数ゲーのときは Python の実行速度面の弱点があまり効かないので、結果的にそこまで不利になっていない感じです。

焼きなまし法などを本格的に使うようになると高速化が本質になってくるので、そうすると Rust などの速い言語を使うのも有効だと思っています。

Q: 並列処理の環境構築するって言ってなかった？

A: まだできてませんごめんなさい。

Q: アクチュアリーをやってるって聞いたけど、業務でプログラミングしてる？

A: 今のところ、業務でプログラミングをすることはないです。

Q: アクチュアリー業務をしていて AHC に有利になることはある？

A: アクチュアリー業務で扱う決算数値や経営成績などの指標は、市場環境や顧客行動などさまざまな要因に影響されます。それを分析や経営判断に生かすため、（専門家ではない）経営陣等にも因果を含めて説明する必要があります。このため、どの事象がどの指標に影響しているかなどのメカニズムを理解し、簡易的に分かりやすくモデル化して説明するという必要性が多くあります。このように問題の本質を崩さない範囲でシンプルに体系化するという作業は、 AHC の評価関数を作る場面などでまさに必要とされることだと思っています。

Q: 新ジャッジコン（ヒュ）の 1.8 乗解法が意味不明なんだけど・・？「(d - last_i) を 2 乗したい」とか「それはやりすぎなので 1.8 乗」について詳しく教えて

A: [tex:(d - last_i)] はこれまでコンテスト $i$ が開催されなかった期間です。コンテストの種類によってコストの係数 $c_i$ が異なるので開催頻度は変わりそうですが、対称性からだいたいこれまでに経過した期間と同じぐらいの期間後に開催されると想定するのが自然ですよね。そこで $c_i * (d - last_i)^{2}$ を使うのが一案になり、これでも十分強いです。

ただこれだと $c_i * (d - last_i)^{2}$ が一致しているものは同等に扱うことになります。実際はこれらの中では $c_i$ が少ない方（ $(d - last_i)^2$ が大きい方）は回収までの日数の期待値が長く上振れを引きやすいことから、将来の大上振れに期待するのが（ $c_i$ が大きい方に比べると）良いことになります。この影響を含めると最適な指数は $2$ 乗より少し小さくなるはずですね。 $1$ 乗や $1.5$ 乗にするほど大きな影響とは思えないので、 $1.8$ 乗ぐらいに最適解がありそうと分かります。