短期AHCで勝つためのテクニック

Transcript

1. 短期AHCで勝つための テクニック Shun_PI (@Shun___PI)
2. 前置き • 短期AHCは戦績を安定させにくい・ 方針ガチャゲーなどと言われることがある • 1位を目指すのであればそうかもしれないが、ある程度の 順位をコンスタントに狙う分には十分安定させることができる • 右図は私の2023年～の短期AHCの戦績 • 7回中4回でTOP10に入っている • 普通に長期AHCより安定していたりする • 成績の良かったコンテストの思考過程を元に 短期AHCで勝つためのテクニックを言語化したい • 特に1位を取るよりも安定して上位に 入ることを目指す • 基本的に問題固有のテクニックよりも 汎用的なテクニックを解説 • 長期AHCでも部分的に参考になるかも？ • 長期は（マラソンマッチ含め）先人が情報を多く残しているので そちらを見るべき
3. 短期AHCで求められる能力 • 実装速度・正確性 • 最重要能力の1つではあるが、訓練で上達させるのは難しい • アルゴレートと相関があるのでアルゴに継続的に参加するのが数少ない訓練法？ • 最重要だけどこのスライドでは対象外 • 方針立て力 • 未知の問題（初めて見た問題）にしてどのようにアプローチするべき？ • このスライドでメインで解説するのはこれ • 天才貪欲力 • 問題を解く簡単かつ強力なルールベース方針を構築できるか？ • 典型力・パターンマッチング力 • 「この手の問題にはこの手法が有効」というパターンマッチングが うまくいく問題は結構存在する • AHCへの継続的な参加・上位解法の復習等の精進で覚える • パラメータチューニング・高速化力 • 上位方針が比較的容易に思いつける問題の場合は順位争いで重要
4. 短期AHCにおける方針立てテクニックの紹介 1. 大方針の選択 • 焼きなましかビームサーチかの選択基準を明確化する • 「最適解から局所的な操作をして、それ以外の部分が依然として最適性を保つか？」 が考察の出発点 2. 中方針の考察 • スコア上限の高い方針から順に考察する • 短期AHCは難易度が低く調整されているので、 最強の解法から考察をはじめて無理そうだと分かってから妥協案を探していく 3. 短期AHCにおける時間配分 • 開始1h~2h以内に方針チェックのためにできるだけシンプルなコードを提出する • 初提出時の順位を生かして大方針・中方針が当たっているかどうかを判断する
5. 大方針の選択 フローチャート START 山登り系問題か？貪欲系問題か？ 不完全情報ゲーム （インタラクティブ問題）か？ モンテカルロ法 焼きなまし YES NO ビームサーチ 貪欲 山登り系問題の特徴 • 解の一部を変化させても 他の部分に影響を与えない （文脈が弱い） • 操作が可逆的である • 貪欲があまり強くない • 行動やターンの概念がない • 「～な条件を満たす最も～な 状態を作れ」など 貪欲系問題の特徴 • 解の一部を変化させると 他の部分が大きく影響を受ける （文脈が強い） • 強い貪欲がある （＝強い行動評価値が作れる） • 序盤に順位表の上位に アルゴ強い人が同点で並ぶ • 強い盤面評価値が作れる （＝ビームサーチの条件） 山登り系 貪欲系
6. 大方針の選択 「文脈」とは何か • ある解の一部を適当に変化させても、 そこから離れた場所を最適な状態に保てる→文脈が弱い • AHC024では、解の一部を局所的に変化させても、 それ以外の部分が依然として最適な状態に保たれるので、文脈が弱い • AHC021では、操作を1つ変えると、以降の操作が全て影響を受け 最終盤面が全く変わってしまうので、文脈が強い • AHC009、032あたりは、文脈があるものの局所変化の影響が比較的弱く、 焼きなましとビームサーチどちらが強いか判断しづらい • 基本的には焼きなましの方が優秀かつ実装が軽いので 焼きなましからトライしてみるのが無難 • 文脈が弱い問題ほど、局所探索法（焼きなまし）が 強力になり、貪欲では歯が立たない • 逆に文脈が強い問題ほど局所探索ができない →網羅的な探索が困難になるため、相対的に貪欲が強くなる • 定量的な指標として、最適解に近傍を適用した際に 「解の何%が最適なまま維持されるか」を考える • 解の99%以上が維持されるならほぼ焼きなまし確定 • 解の90%が維持されるあたりがボーダーライン？ • ターン制ゲーム系は50%（現在より前のターン）しか維持されない
7. 大方針の選択 過去のAHCにおける方針の集計 • 2024/5までの過去の短期AHC16回における（コンテスト中の）上位方針 • 焼きなまし：9回 • 「とりあえず焼きなまし」と考えておけば大体当たる • ビームサーチ：2回 • 021, 032 • 貪欲：2回 • 004, 026 • 貪欲の重要度が非常に高く（ビームサーチ化も困難で）貪欲のみでコンテスト中最上位になれる 026延長戦ではビームサーチが上位（004は良く分からない） • ちなみに2時間コン（昔の日本橋ハーフマラソンなど）では貪欲だけで最上位になれる問題は かなり多かったが、短期AHCでは割と珍しい • モンテカルロ法（貪欲プレイアウト）：3回 • 007, 015, トヨタfinal • いずれも不完全情報ゲーム（インタラクティブ問） • 今のところ短期でインタラクティブが出たらモンテカルロ法安定 • HTTF本戦などを含めるとその限りではないので確定ではない（推定系問題など） • 参考：thunderさんのAHC解法まとめ • https://docs.google.com/spreadsheets/d/16i1Z-151b2c3dmiPqPzkoMJp5_ilR83TJGNi6iioUPo/edit#gid=676011584 • 全問ちゃんと見てるわけではないので間違ってるかも
8. 短期AHCにおける方針立てテクニックの紹介 1. 大方針の選択 • 焼きなましかビームサーチかの選択基準を明確化する • 「最適解から局所的な操作をして、それ以外の部分が依然として最適性を保つか？」 が考察の出発点 2. 中方針の考察 • スコア上限の高い方針から順に考察する • 短期AHCは難易度が低く調整されているので、 最強の解法から考察をはじめて無理そうだと分かってから妥協案を探していく 3. 短期AHCにおける時間配分 • 開始1h~2h以内に方針チェックのためにできるだけシンプルなコードを提出する • 初提出時の順位を生かして大方針・中方針が当たっているかどうかを判断する
9. 中方針の考察 スコア上限の高い方針から順に考察する • 大方針が決まったら次に中方針を考察していく • 原則として「スコア上限の高い方針」から順に検討する • 最終的なスコアができる限り理論値に近くするにはどうすればよいか？を念頭に置く • 山登り系問題の場合、 「自主制約無し・高速な近傍とスコア計算の焼きなまし」が最強 （＝スコア上限最大の方針） • AHCにおけるあらゆる方針の中でも最強なので、迷ったらまずここへの帰結を試みる • 自主制約とは、「このような解は考えなくて良い」「このような操作はしなくて良い」のような 直感を生かして探索空間を狭めることで探索効率を上げる手法だが、考察序盤に決め打つのは厳禁 • 貪欲系問題の場合、高速な盤面評価値を生かしたビームサーチが最強 • 貪欲系問題と分かった時点で盤面評価値の構築を頭に置く • 焼きなましとビームサーチで迷ったら原則焼きなましの方が強いので先に試す • 方針の確度や実装の難度的に不可能と判断した場合、徐々にスコア上限を下げながら考察する • 短期AHCは難易度が時間に対して適切になるような調整されていて（いるはず） 、 理論値に遠く及ばない盤面が最上位解法となるような問題は少ない • 完全なメタ読みではあるが、あまりにも難易度が高い問題を短期で出すと ルールベース構築バトルになり、AHCの理念にあまりそぐわなくなるので、 適度な難易度に調整されると信じてよい（はず）
10. 中方針の考察 焼きなましの中方針考察 高速な近傍・スコア計算で、 自主制約なし（任意の盤面）で焼けるか？ 自主制約があれば焼けるか？ 巨大な近傍なら焼けるか？ （部分破壊再構築） スコア計算がO(N)なら焼けるか？ 禁止された状態への遷移を ペナルティ込みで許容すれば焼けるか？ 方針確定 問題によって考察すべき 候補は異なるが、 原則としてスコア上限の 高そうなものから考える YES NO（すぐに諦めるのではなく、 十分に考えてから諦めるべき） AHCの解法精進をして 典型力を上げておくと ここの精度が高まる 文脈が強くて焼けそうになく強い貪欲が あるのでビームサーチへ向かうか？ …
11. 中方針の考察 貪欲の考察について • 最初の考察では、「理論値（満点）」が取れると信じ、 それに近い形を実現するにはどんな方法があるだろうか？と考えるのがよい • 理論値が無い問題（ターン数最小化問題など）の場合は スコアの上界（最小化の場合は下界）を計算してみると良い • 例えば、問題におけるなんらかの制約を無視して最小ターン数を計算するなど • 最短ルート構築系の問題など、理論値や上限が計算困難な問題も多いが、 とりあえずスコアが高い解を手で模索してみるのも有効 • ただし、ここでスコアの高い解の条件を見誤ると最後までボトルネックとなり得る • 天才貪欲は（分かってしまえば）非常にシンプルなものが多いので、 最初から複雑な手順で考察しようとしない • 軽い貪欲の方がビームサーチやモンテカルロ法が高速 • 残念ながら私に天才貪欲力が無いのであまり解説できない • アルゴ精進や、色んなパズルゲームやボードゲームに触れておくなどが上達法？
12. 短期AHCにおける方針立てテクニックの紹介 1. 大方針の選択 • 焼きなましかビームサーチかの選択基準を明確化する • 「最適解から局所的な操作をして、それ以外の部分が依然として最適性を保つか？」 が考察の出発点 2. 中方針の考察 • スコア上限の高い方針から順に考察する • 短期AHCは難易度が低く調整されているので、 最強の解法から考察をはじめて無理そうだと分かってから妥協案を探していく 3. 短期AHCにおける時間配分 • 開始1h~2h以内に方針チェックのためにできるだけシンプルなコードを提出する • 初提出時の順位を生かして大方針・中方針が当たっているかどうかを判断する
13. 短期AHC(4時間コン)の時間配分 時間配分例（私の場合） 大方針～中方針 考察① 15分～60分 大方針～中方針 実装① 15分～60分 大方針～中方針 考察② 15分～30分 大方針～中方針 実装② 15分～30分 小方針考察＆ 実装×n 60分～120分 パラメータ チューニング 定数倍高速化 15分～60分 ①で決定 ①を捨てて②を試す 良さそうな アイデアが 尽きたら ビジュアライザを見つつ アイデア探し ※もちろんこれが最適な時間配分というわけではなく、 最初にじっくり考察したい人とか 実装速度の違いなどに応じて色々あると思う 提出時順位表で判断
14. 短期AHC(4時間コン)の時間配分 大方針～中方針を1回で決定した場合の例 • 大方針～中方針の考察と実装を 1回で完了した例 • 開始1~2時間の提出直後に かなり高い順位を得ている • どのくらい高い順位を得ていれば良いかは 個人の実装速度によるが、十分高い順位に 付けたと思ったら自信をもって 大方針～中方針をfixする https://iilj.github.io/AtCoderMarathonReplay/#/chart/ 時間 方針 fix度 順位
15. 短期AHC(4時間コン)の時間配分 大方針～中方針を1回で決定しなかった場合の例 • 大方針～中方針の考察と実装を 複数回行った例 • 例えばAHC032では19:30に焼きなましを 提出するも一瞬で順位を落としている • これを見て方針を切り替えて20:30に 貪欲を、21:30以降にビームサーチの 実装を行い終盤に順位を上げた • 短期AHCの初提出時（開始1h~2h程度）の順位と 大方針・中方針を当てていることの相関はかなり 高く、 方針をどこまでfixするかの指標として重要 • 長期AHCと比較しても、みんなが よーいドンで考察し始めるので各個人の 努力量が統一され順位の信頼度が高い https://iilj.github.io/AtCoderMarathonReplay/#/chart/ 時間 方針 fix度 方針 fix度 順位
16. 短期AHCにおける汎用テクニックの紹介 1. 大方針の選択 2. 中方針の考察 3. 短期AHCにおける時間配分 以上のテクニックを使って、短期AHCの問題5つについて考察過程を考えてみる • （各問題の概要はものすごく簡略化してあるので、 詳細を知りたい方はコンテストページを見てください） • 上位解法が分かった上で書いているので、実際のコンテスト中に同じ考察過程が できることを保証するものではありません
17. AHC028 （全てがうまくいったケース） 問題概要 • 15*15のグリッド上を動いて 与えられた200個の文字列を すべて含む文字列を作れ • できるだけ移動距離を短くせよ • ★「高速な近傍・スコア計算で自主制約なし」の 焼きなましが可能か？（スコア上限最大の方針） • 単語の訪問順を焼きなます（自然な焼きなまし） • 単語のswapを近傍とするとこれはO(1)なので高速な近傍 • 最適解からswapをした際95%以上の文字列に関して最適に保たれる （文脈が弱い）ので、焼ける • これは厳密に証明するのは難しく、ビジュアライザからの直感による • 盤面が大きかったりアルファベットの種類数が少ないと焼けなくなりそう • 高速なスコア計算は可能か？ • 同じアルファベットが複数あるため、単純には出来ない • 毎回DPすれば計算できそうだけど、遅いので一旦保留 • 開始位置と終了位置を固定すれば各単語について最小コストが前計算できそう • じゃあ単語の終了位置を焼きなましの状態に追加すれば？ • 高速なスコア計算ができそう！ • ★が可能と分かったので大～中方針の考察終了 • 本番ではここまで考察時間10分程度 • 開始1時間15分で提出時1位・本番29位相当の提出に成功 • 近傍の追加と高速化次第で本番優勝まで狙えた
18. AHC032 （方針転換でうまくいったケース） 問題概要 • 9*9のグリッドに 3*3のスタンプを押していく • スタンプを押すと mod998上で数値が加算される • できるだけ全てのマスの 数字の総和を大きくせよ • ★「高速な近傍・スコア計算で自主制約なし」の 焼きなましが可能か？（スコア上限最大の方針） • スタンプの種類と位置を焼きなます（自然な焼きなまし） • スタンプの追加・削除・種類の変更・位置の移動などの近傍がありそう • 最適解から操作を行うと、大体9マス程度が最適から大きく離れた状態になる • 9割位は最適なまま残るが、焼きなましかビームサーチか判断が難しい • 焼きなましなら20分あれば実装できそうのでとりあえず書いて提出 • 迷ったら焼きなまし優先の原則 • 提出時順位表をチェックし、あまり順位が良くないことを確認 • 焼きなましは出来ないと判断し大方針を捨てる • アルゴが強い人が上位に多くいるため、貪欲方針を考える • 位置毎にスタンプの全探索をしてマスを1つずつ確定させていく貪欲が見つかる • 確定したマスの数字の和が盤面評価値として有効と思われるため、 ビームサーチで方針確定 • 焼きなましを書いて提出するまで30分程度（本番500位相当） • 貪欲を書いて提出するまで+40分程度（本番200位相当） • ビームサーチを書いて提出するまで+80分程度（本番120位相当） • この時点ではあまり順位は良くなかったが、 最終的なトップ解法と同じ大方針にたどりつき、 ここからのアイデアによる改善で本番9位まで上げることができた
19. 11周年記念企業対抗Team Battle （文脈の強さを見誤ったケース） 問題概要 • 壁にぶつかると右に曲がる 車を走らせる • 壁を自由に設置して車が 無限ループに陥るまでの ターン数をできるだけ長くせよ • ★「高速な近傍・スコア計算で自主制約なし」の 焼きなましが可能か？（スコア上限最大の方針） • 壁の設置・削除を近傍として焼きなます（自然な焼きなまし） • 壁を変化させると、「車がそこに到達した以降の動き」が変わってしまうので、 文脈が強い？？？ • ここの判断ミスで焼きなましに対して迷いを生んだことが本番の敗因の一つ • 実はこの問題には「強い壁の配置パターン」が存在し、 仮に操作によってパターンに入れなくなり一時的にスコアが下がっても、 何回かの操作により再び強い壁のパターンに入れれば 高いスコアの状態に遷移できる • すなわち最適解で操作した部分以外の最適性が保たれていると言えるため、 実は文脈が弱く焼きなましができる • 近傍は高速だが、スコア計算の高速化はかなり難しそうなので妥協 • スコア計算を高速化しなくても、各種焼きなましの高速化や 操作するマスの選択効率化などにより本番1位は達成可能 • スコア計算の高速化としては、ルートが同じ部分の使いまわしや 枝刈りによる計算の強制終了などがありそう（やっていないので分からない）
20. AHC021 （スコア上限最大の方針に従わず中方針を間違えた） 問題概要 • ピラミッド状の盤面に数字が ランダムに割り振られている • 隣り合った数字のswapができる • できるだけ少ないswap回数で 各数字の斜め上に自分より 大きな数字が来ないようにせよ • 焼きなましが可能か？ • 無理そう（ターン性で状態がどんどん変化していくタイプのゲームなので） • 序盤にアルゴ強い人が順位表上位に同点で並ぶ(13,426,585) • 天才貪欲を考える • ここは色々手で試しながら頑張るしかない • 「0から順にできるだけ上に上げていく」 「上に上げる際に同時に大きい数字を押し下げる」という 強い解の条件を（気合で）見つける • 「上に上げていく過程で下に押し下げた数字の総和」が 盤面評価値として有効そうなので、ビームサーチができそう • 1swapを1ターンにするか、1つの数字を上に上げるまでを1ターンにするか 選択がある • ビームの時間軸方向は細かい方がスコア上限が高いので 1swap1ターンでまず考察すべき（1位・2位解法） • 1数字1ターンでもまあまあ強い（AHCラジオによると本番5位くらい） • 本番では上記の2つの要点の考察に成功していたにもかかわらず、 ビームサーチを考察せずに部分破壊乱択山登りをしてしまった （ビームサーチよりスコア上限の低い解法） • それでも本番9位 • だが、もしビームサーチができれば（このスライドの考察方針を守れれば） 本番5位以内が狙えていた
21. AHC015 （天才貪欲・インタラクティブ・本番で惨敗） 問題概要 • 飴がランダムな場所に出現する →上下左右に盤面を傾ける を繰り返す • 最終盤面において同じ種類の飴を できるかぎり連結させよ • インタラクティブなので、モンテカルロ法（プレイアウト） • 推定系っぽかったら考え直すべきかも • 例えば正規分布からサンプリングされるパラメータが存在するなど • （今のところ短期AHCで推定系はでていない） • できるだけ速く強い貪欲をとにかく作りたい • 順位表を見ることで簡単で強い貪欲がありそうなことが分かる • 原則：理論値盤面を考える • なぜなら、短期AHCの難易度は調整されており、理論値盤面からほど遠い バラバラな状態がトップ解法にならないようになっているから（メタ読み） • 各連結成分は細長くなるより正方形や円形に近い方がよさそう • 連結成分が切れにくいので • 右下図のようにイメージすると、 上左右に各色を割り当てられそう（難しい） • ここからマニュアルモードで気合で天才貪欲を確立する（超難しい） • 複雑な手順の貪欲を考えようとしない （複雑で低速な貪欲はプレイアウトで結局弱いので） • 天才貪欲が分かればあとは貪欲プレイアウトをやるだけ • eijirouさんの記事だと、本番4位相当らしい • thunderさんの記事だと（乱数の固定化を使って？）本番1位相当
22. まとめ • 短期AHCにて汎用的に使える方針立てテクニックを紹介した • 問題固有・ミクロなテクニックは対象外とし、マクロな戦略を説明した • 特に「序盤の考察や方針立てはシステマティックに行える」というのが一番伝えたいこと • この手の攻略法が確立されてくると実装力の差で私が勝てなくなってくる気はするのだが、 それを気にするよりはAHCを布教する方が大事だと思っている • なんだかんだで問題固有部分の考察のウェイトが大きいことも多く、 問題の本質が見抜けないと勝負にすらならない問題も多い （特に貪欲系問題）ので、常に万能なテクニックというわけではない • 実装速度や実装正確性（バグの少なさ）ははっきり言って 短期AHCで最重要能力なのだが、これを伸ばす楽な方法はない • 実装速度が上がれば大方針やアイデアを試す個数が増える • 実装正確性が上がればバグ修正による時間の浪費やバグによるスコアの悪化を防げる これとか これとか
23. 次回の短期AHC • 2024/6/16 (日) 15:00~19:00 • トヨタ自動車プログラミングコンテスト2024#6（AHC034） • 2024/7/21 (日) 15:00~19:00 • ALGO ARTISプログラミングコンテスト2024夏 (AHC035) • 短期が2回続くので、是非スライドの内容を生かしてみてください！