# マラソン # TODO PACEの論文(記事？)を読む https://github.com/rhoo19937/p/blob/main/tech/.md を読む MCMC variable neighborhood search heuristic ベイズ推定(https://platinum-prog.hatenablog.com/entry/2023/05/20/231200) AHC014 wataさん // ランダムに最大4つ候補を取り出す // 最初の一手は最初に取り出した候補で決定 // 沢山消しすぎるとまともに再構築出来る確率が低い上に時間がかかるので選び直し // ランダムな中心(cx,cy)からランダムなマンハッタン距離wの範囲にある印を全削除 ## 汎用テクニック ### 同じパラメータで入力を大量生成して、採用するアルゴリズムを決める - [AtCoder Heuristic Contest 025](https://atcoder.jp/contests/ahc025/tasks/ahc025_a) komori3さん(117位) - [本人の参加記](https://github.com/komori3/AHC025) - "LDM と LPT のよい方（入力と同じ N,D,Q で大量に生成した問題を 1.7sec 解いて、平均的に良かった方）を採用するようにして最終提出した" ### 入力を変更して扱いやすいパラメータに変更 - うまく書けない - [トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）Stack of Boxes](https://atcoder.jp/contests/ahc026/tasks/ahc026_a) SI_AtCoderさん(386位) - Nが小さい場合のアルゴリズムを用意する。Nが大きい場合、2つ組にしてNを小さくする。 ### 緩和した問題(or 部分問題)を解き、それを参考にする - 下の`条件を緩和した問題の解から実行可能解を求める`をもっと抽象化したもの - [トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033） Container Handling with Cranes](https://atcoder.jp/contests/ahc033/tasks/ahc033_a) bowwowforeachさん(暫定1位) - 一時的に置く回数を最小化する問題をDPで解き、ビームサーチに使用する。少し最適から落ちるものも許容する ## 高速化 ### bit演算 - [Rotated BitBoardとMagic Bitboardの説明](https://ipsj.ixsq.nii.ac.jp/ej/index.php?active_action=repository_view_main_item_detail&page_id=13&block_id=8&item_id=71312&item_no=1) - [estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014） RectJoin](https://atcoder.jp/contests/ahc014/tasks/ahc014_a) terry_u16さん(3位) - [本人の参加記](https://github.com/terry-u16/ahc014/blob/master/diary.md) - 2日目にRotated BitBoardを実装している - [トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033） Container Handling with Cranes](https://atcoder.jp/contests/ahc033/tasks/ahc033_a) bowwowforeachさん(暫定1位) - [ビットボードで現在位置から目的地までにかかるターン数を計算](https://x.com/bowwowforeach/status/1795063661502873628) - 事前計算すればいいのでは？と思ったが、クレーンがあっても計算できるらしい。賢い点…… ### 固定長配列を複数個宣言しておき、必要なものだけを使う - [komoriさんのツイート](https://twitter.com/komora71_/status/1542244070088511488) ### グリッドグラフの連結チェックの際、周囲$3\times 3,5\times 5$領域のみを見る - 十分条件(より厳しいが、早く確認できる条件)で判定する感じ - [第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023） Crops on Grid](https://atcoder.jp/contests/ahc023/tasks/asprocon10_a) Shun_PIさん(4位) - [解説スライド](https://speakerdeck.com/shun_pi/ahc023can-jia-ji-zan-ding-ban-shou-shu-kitu-duo-me?slide=18) ### 初期化が速い配列 - [BFSを繰り返すときに訪問済みかを記録する配列を毎回初期化しなくて良くするアレ](https://topcoder-tomerun.hatenablog.jp/entry/2022/11/06/145156) ### グリッド問題の隣接点を事前計算 - もっと広く見て事前計算としてもいいかも - 高速化より実装のストレスが減る方が大きいかも - [bowwowforeachさんのツイート](https://twitter.com/bowwowforeach/status/1437396768023404548) ## 焼きなまし ### 局所解にハマっている原因を調査する - [丸紅プログラミングコンテスト2023（AtCoder Heuristic Contest 024） Topological Map](https://atcoder.jp/contests/ahc024/tasks/ahc024_a) susuzumeさん(1位) - [本人のツイート](https://twitter.com/tomatobokujo/status/1705887974716801501) - "隣り合う1マスを塗る遷移と隣り合う2マスを塗る遷移の焼き鈍しをしました。1マスだけだと0002と0003で固まってしまうところがあったので2マスの遷移も追加しました。" - [wataさんの解説ツイート](https://twitter.com/wata_orz/status/1705887357965340979) - "あるマスの色を隣接マスの色に変更するという近傍だけだと十字型に区切り線が入っているところで動かせなくなって詰むので、2マス同時に変更すると上手く行きました" ### 徐々に変化量を狭める - [焼きなまし法のコツ Ver. 1.3 「序盤は大きく変化、終盤は小さく変化させたほうがいい」](https://shindannin.hatenadiary.com/entry/2021/03/06/115415) ![](https://hackmd.io/_uploads/Sk8bE2seT.png) - [AtCoder Heuristic Contest 002(AHC002) Walking on Tiles](https://atcoder.jp/contests/ahc002/tasks/ahc002_a) ats5515さん(1位) - [本人のツイート](https://twitter.com/ats5515/status/1386326149307932672) - "パスを切る長さをだんだん狭める。" - [THIRD プログラミングコンテスト2024（AtCoder Heuristic Contest 039）　Purse Seine Fishing](https://atcoder.jp/contests/ahc039/tasks/ahc039_a) terryさん(1位) - [本人のツイート](https://x.com/terry_u16/status/1855552971045789937) - "最初は10x10のグリッドから始めて、20x20→40x40→……→320×320と少しずつ細かくしていきました。近傍はマスのon/off切り替えだけ" - 最後のひと押しの改善ってイメージだったけどこの工夫があるからこそ、この近傍でいけてる気がする ### すべての近傍のスコア変化量を保持して、受理される近傍をランダムに選ぶ - 遷移によって、スコア変化量が変わる近傍が少ない場合は強そう - [hakomoさんのツイート](https://twitter.com/hakomof/status/903787570655502336) - どの問題に対してのアルゴリズムか分からない ### 近傍を大きくする - [詳解 焼きなまし法 近傍を大きくする](https://github.com/hakomo/Simulated-Annealing-Techniques/blob/master/%E8%BF%91%E5%82%8D%E3%82%92%E5%A4%A7%E3%81%8D%E3%81%8F%E3%81%99%E3%82%8B.md) - 一部を破壊して(山登りや貪欲で)再構築 - 貪欲で再構築する際、ランダム性を入れるとよさそう(評価値に$\epsilon$を足したり掛けたり) - [AtCoder Heuristic Contest 001 AtCoder Ad](https://atcoder.jp/contests/ahc001/tasks/ahc001_a) bin101(45位) - 遷移は2つあって、①どこかの辺の長さを1変える②ある広告を選んで、それとそれに接している広告を初期解に戻して①の山登り(ツイートから抜粋) - 高速化と多様性確保のために、辺を増やす量を512にして、山登りできなくなった時点でその量を1/2するのを繰り返す - [estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014） RectJoin](https://atcoder.jp/contests/ahc014/tasks/ahc014_a) bowwowforeachさん(1位) - [本人の参加記](https://bowwowforeach.hatenablog.com/entry/2022/10/03/221631?_ga=2.146070644.1334717408.1664750310-1509622582.1661469029) - "ランダムに四角を1個削除～それに依存する四角も全部削除したあと、貪欲に四角を作れるだけ作る、というのを繰り返します。" - [集合被覆問題](https://www.msi.co.jp/solution/nuopt/docs/examples/html/02-06-00.html) [Note: A local-search heuristic for large set-covering problems](https://onlinelibrary.wiley.com/doi/abs/10.1002/1520-6750(199510)42:7%3C1129::AID-NAV3220420711%3E3.0.CO;2-M) - 近傍: 解の一部を削除する。カバーできていない要素をランダムに選んで、それを含んでいる集合の中で「新しくカバーできる箇所の個数/コスト」が最大のものを選ぶ貪欲で再構築。解の中に削除できるものがあれば削除 - [Graph Partition](https://en.wikipedia.org/wiki/Graph_partition) [Kernighan–Lin algorithm](https://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm) - 「貪欲に2つを入れ替える」操作を$|V| / 2$回まで行い、スコアが最大となるところまでを実際に行うのを繰り返す - [丸紅プログラミングコンテスト2023（AtCoder Heuristic Contest 024） Topological Map](https://atcoder.jp/contests/ahc024/tasks/ahc024_a) rhooさん(延長戦順位表1位) - [本人のツイート](https://twitter.com/rho__o/status/1707043053394084285) - "dfsで有効なn点changeを求める" ### 変化量を指数分布にする - 2つの利点(高速化と局所解にハマりにくくなる)がありそう - [terryさんのツイート](https://twitter.com/terry_u16/status/1723610929684996535) - "値の範囲が10^5とかのときは±1とかの近傍にする代わりに±pow(10, X)としてXを[0.0, 4.0]とかかからランダムに選んだりするとよい" - [AtCoder Heuristic Contest 001 AtCoder Ad](https://atcoder.jp/contests/ahc001/tasks/ahc001_a) ymatsuxさん(2位) - [本人のツイート](https://twitter.com/ymatsux_ac/status/1371060070449090561) - "拡大量は [1, 10000] の範囲から指数分布でサンプルする" ### パスグラフの近傍 - 部分パスを削除して、繋ぎなおす - AHC002 tomerunさん(3位) - https://twitter.com/tomerun/status/1386320639120658433 - AHC010 bin101(25位) ### 木グラフ(連結グラフ)の近傍 - AHC023 ynasuさん(5位) - 追加する頂点をランダムに選ぶ。shortest pathでグラフにつなげる - 削除する頂点をランダムに選ぶ。これにより、連結ではなくなった頂点は削除 ### 高速化 - diff>log(rand)*temperatureの右辺を事前に計算しておいて近傍のスコア計算の枝刈りに利用する - https://qiita.com/not522/items/cd20b87157d15850d31c - diffの上界を早く求められる際に効く - expを前計算しておいて近似値で妥協 - [明らかに悪い結果はexpを計算せずにfalseを返す](http://web.archive.org/web/20200105011004/https://topcoder.g.hatena.ne.jp/tomerun/20171216/) - ### 高度な(?)知識を使って高速化 - [Marathon Match 119](https://www.topcoder.com/challenges/9a7c7da8-dcec-4fa2-8581-7d5774b52d1b) c7c7さん(2位) - LinkCutTreeを使って高速化。 - [本人のツイート](https://twitter.com/C7C7LL/status/1291125625235763201) - [AtCoder Heuristic Contest 011 Sliding Tree Puzzle](https://atcoder.jp/contests/ahc011/tasks/ahc011_a) eivourさん(36位) - [本人のツイート](https://twitter.com/contramundum2/status/1533442163685502976) - 二部マッチングの差分更新を1回のダイクストラで行う - [参考になる論文](https://arxiv.org/abs/2208.11325) ### 一部をアルゴに任せる - [hakomoさんの記事「状態を2分して同時に最適化する」]( https://github.com/hakomo/Simulated-Annealing-Techniques/blob/master/%E7%8A%B6%E6%85%8B%E3%82%922%E5%88%86%E3%81%97%E3%81%A6%E5%90%8C%E6%99%82%E3%81%AB%E6%9C%80%E9%81%A9%E5%8C%96%E3%81%99%E3%82%8B.md) - [RECRUIT 日本橋ハーフマラソン 2021 B](https://atcoder.jp/contests/rcl-contest-2021/tasks/rcl_contest_2021_b) phocomさん(2位) - 使うマスの集合を焼きなまし。パワーは簡単に最適解が求まる - [本人のツイート](https://twitter.com/_phocom/status/1431544438807875586) - [RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）Server Room](https://atcoder.jp/contests/ahc013/tasks/ahc013_a) bowwowforeachさん(1位) - コンピュータの位置を移動させる焼きなまし。ケーブルは貪欲(最適解ではない) - [本人の参加記](https://bowwowforeach.hatenablog.com/entry/2022/08/18/205537?_ga=2.89825881.310502845.1660691221-2017915354.1639952297) ### 探索空間を意図的に狭める - [詳解 焼きなまし法-状態を単純な構造に限定する](https://github.com/hakomo/Simulated-Annealing-Techniques/blob/master/%E7%8A%B6%E6%85%8B%E3%82%92%E5%8D%98%E7%B4%94%E3%81%AA%E6%A7%8B%E9%80%A0%E3%81%AB%E9%99%90%E5%AE%9A%E3%81%99%E3%82%8B.md) - [AtCoder Heuristic Contest 012 AtCoder 10th Anniversary](https://atcoder.jp/contests/ahc012/tasks/ahc012_a) assyさん(2位) - 斜めの線を考えない。こうすることで、スコア計算の高速化ができる(高速化以外の恩恵もありそう？) - [本人の参加記](https://assy.hatenablog.jp/entry/2022/07/04/001918) - [Marathon Match 119](https://www.topcoder.com/challenges/9a7c7da8-dcec-4fa2-8581-7d5774b52d1b) - 空きマスが木の場合のみを考える ### 良さそうな近傍しか見ない - [THIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017） Road Repair](https://atcoder.jp/contests/ahc017/tasks/ahc017_a) wataさん(延長戦順位表9位) - [自分のツイート](https://twitter.com/5bin101/status/1623312241981521920) - "「山登りの近傍でランダムな日付に変えるんじゃなくて、隣接する辺の日付に変える」" ### 悪い状態を除く - 探索空間を意図的に狭める、と似ている - [詳解　焼きなまし法　悪い状態を除く](https://github.com/hakomo/Simulated-Annealing-Techniques/blob/master/%E6%82%AA%E3%81%84%E7%8A%B6%E6%85%8B%E3%82%92%E9%99%A4%E3%81%8F.md) - [京セラプログラミングコンテスト（AtCoder Heuristic Contest 006） Food Delivery](https://atcoder.jp/contests/ahc006/tasks/ahc006_a) - 中心点から遠い点を無視する ### 近傍の種類によって、log(rand)*temperatureの値を変える - [第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023） Crops on Grid](https://atcoder.jp/contests/ahc023/tasks/asprocon10_a) ynasuさん(5位) - 収穫の日を増やす近傍のlog(rand)*temperatureを0.2倍にしていた(つまり、遷移しにくくなる) ### 制約をペナルティ関数に押し付ける - [焼きなまし法のコツ Ver. 1.3 「制約条件がある問題では、スコア関数にペナルティをつける。」](https://shindannin.hatenadiary.com/entry/2021/03/06/115415) ![](https://hackmd.io/_uploads/B1gzf3se6.png) ### ペナルティ関数をつける - [焼きなまし法のコツ Ver. 1.3 「スコアが改善しやすくなるようなスコア関数を決める。」](https://shindannin.hatenadiary.com/entry/2021/03/06/115415) ![](https://hackmd.io/_uploads/HJcEDhjgp.png) -　生スコアに反映されない(にくい)が、良い解が近くにある確率を上げる要素を考慮するため(上手くかけない) - [RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）Server Room](https://atcoder.jp/contests/ahc013/tasks/ahc013_a) bowwowforeachさん(1位) - [本人の参加記](https://bowwowforeach.hatenablog.com/entry/2022/08/18/205537) - "このスコアに、以下のペナルティをかけたものが最終的な評価値となります。ペナルティ量は時間で減衰させ最終的に0にします。" - 行動回数が多いほど減点 - 移動回数が多いほど減点 - コネクタ長が長いほど減点 ### 汎用テクニック - 多点スタート - 一定期間更新なしの場合、最高値にロールバック - 高速化 ## 貪欲 ### 評価値のパラメータを焼きなまし - [TOYOTA Programming Contest 2023 Summer final Transit Warehouse](https://atcoder.jp/contests/toyota2023summer-final/tasks/toyota2023summer_final_a) terryさん(1位) - 「取れるコンテナのうち、一番優先度の高いものを取る」貪欲。この優先度を焼きなまし - [本人の解説記事](https://www.terry-u16.net/entry/toyota2023summer-final) - ビームサーチより実装が楽なのがよさそう - [トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026） Stack of Boxes](https://atcoder.jp/contests/ahc026/tasks/ahc026_a) fuppy0716さん(25位) - [本人のツイート](https://twitter.com/fuppy_kyopro/status/1721106888363048992) - "「箱 x を回収するために箱 x の上に載っている箱たちをどの山 y に動かすか」を全ての箱について決めうち、y を変化させる焼きなましをしました。焼きなましのイテレーションごとに愚直にシミュレーションを回してスコア計算をしました。" - 実装楽そう ### 1ターン目から最終ターン目まで、操作を変えてスコアが改善されたら採用を繰り返す - 評価値を貪欲のシミュレーションにした、と考えた方が自然か - [TOYOTA Programming Contest 2023 Summer（AtCoder Heuristic Contest 021） Pyramid Sorting](https://atcoder.jp/contests/ahc021/tasks/ahc021_a) oteraさん(16位) - [本番33位相当の得点が得られる簡単なアルゴリズム by otera](https://atcoder.jp/contests/ahc021/editorial/6686) ### ビームサーチにする - [第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023） Crops on Grid](https://atcoder.jp/contests/ahc023/tasks/asprocon10_a) bin101(18位) - 貪欲が強いからビームサーチにした。最終提出は幅12で42.4M。貪欲に戻すと42.1M。 ## ビームサーチ ### 将来かかるターン数の下界を評価値にする - [トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033） Container Handling with Cranes](https://atcoder.jp/contests/ahc033/tasks/ahc033_a) じろうさん(暫定4位) - かなり深く考察している - [本人の解説記事](https://shuu0914.hatenablog.com/entry/2024/05/27/190612) ### 完成までの最短手数を求める - ビームサーチを信じる - [トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033） Container Handling with Cranes](https://atcoder.jp/contests/ahc033/tasks/ahc033_a) じろうさん(暫定4位) - [本人の解説記事](https://shuu0914.hatenablog.com/entry/2024/05/27/190612) - [AtCoder Heuristic Contest 011 Sliding Tree Puzzle](https://atcoder.jp/contests/ahc011/tasks/ahc011_a) 多くの上位陣 ### 遷移を分解する - [トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033） Container Handling with Cranes](https://atcoder.jp/contests/ahc033/tasks/ahc033_a) じろうさん(暫定4位) - 愚直に1ターンの行動を遷移とすると、移動だけを考えても$5^5$通りあり、多様性が失われそうだし、計算時間もかかる - クレーン1体の行動確定を遷移とする - [本人の解説記事](https://shuu0914.hatenablog.com/entry/2024/05/27/190612) ### 評価関数に良し悪しが反映されるものはハッシュに組み込まない - [トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033） Container Handling with Cranes](https://atcoder.jp/contests/ahc033/tasks/ahc033_a) じろうさん(暫定4位) - [本人の解説記事](https://shuu0914.hatenablog.com/entry/2024/05/27/190612) - クレーンのX座標をハッシュでは区別しない ### 条件を緩和した問題の解から実行可能解を求める - [トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033） Container Handling with Cranes](https://atcoder.jp/contests/ahc033/tasks/ahc033_a) Rafbillさん(暫定17位) - [本人のツイート](https://x.com/Rafbill_pc/status/1795144513410785774) - コンテナの衝突を無視した解からビームサーチで実行可能会を求める(大体0~4増えるらしい) - [Santa 2022 - The Christmas Card Conundrum](https://www.kaggle.com/competitions/santa-2022/discussion/379167) nagissさん(4位) - [解説記事](https://www.kaggle.com/competitions/santa-2022/discussion/379080) - TSPを解いて、それを達成するようなアームの動きをビームサーチで求める - 求められるようにTSPに制限を加えている ### 評価関数を工夫する - [トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033） Container Handling with Cranes](https://atcoder.jp/contests/ahc033/tasks/ahc033_a) wataさん - [解説動画](https://www.youtube.com/watch?v=DUWfVeIRjCU) - 最大値を最小化したい問題。 - 最大値を評価関数にした場合: 最大値以外は適当になってしまう - 平均値を評価関数にした場合: 最大値+5と最小値+5が同じ価値になってしまう - 重み付け平均をとる。1番低いもの: 0.05,2: 0.1,3: 0.15,4: 0.20,5: 0.50 ## 評価値 ### モンテカルロ - ランダム性がある場合に使われる - シミュレーション時に使う貪欲の強さに強く影響される - [TOYOTA Programming Contest 2023 Summer final Transit Warehouse](https://atcoder.jp/contests/toyota2023summer-final/tasks/toyota2023summer_final_a) terryさん(1位) - 荷物が入ってくる順番がランダムだからモンテカルロを使っている。 - [本人の解説記事](https://www.terry-u16.net/entry/toyota2023summer-final#%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E3%82%B7%E3%83%9F%E3%83%A5%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%82%92%E3%81%99%E3%82%8B3h00m) - "まずは搬入パートから説明します。モンテカルロシミュレーションを行っていくのですが、まずは強い貪欲を作るのが超大事です。この貪欲の性能で全体の性能が決まります。" - [トヨタ自動車 プログラミングコンテスト2022（AtCoder Heuristic Contest 015） Halloween Candy](https://atcoder.jp/contests/ahc015/tasks/ahc015_a) eijirouさん(1位) - 強い貪欲+ランダム性だからモンテカルロが最強！って感じなのかな - [本人の参加記](https://eijirou-kyopro.hatenablog.com/entry/2022/11/03/172820?_ga=2.150583857.685130743.1667373871-1742515623.1634302507) ### 問題の実スコア関数の特徴を捉える - [RECRUIT 日本橋ハーフマラソン 2021 A](https://atcoder.jp/contests/rcl-contest-2021/tasks/rcl_contest_2021_a) - [解説動画](https://www.youtube.com/watch?v=4bW66DJsGF8) - スコア関数がlogだから、平均を小さくするより、少数を0に近づけた方がいい - [RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）Server Room](https://atcoder.jp/contests/ahc013/tasks/ahc013_a) - 2乗に比例するから1種類の大きいものを作ることに拘った方がいい ### シミュレーション - 実際のものより有利（不利）なものになっているのならそれを考慮した方がいい - [THIRD プログラミングコンテスト 2021 （AtCoder Heuristic Contest 007）Online MST](https://atcoder.jp/contests/ahc007/tasks/ahc007_a) bin101(3位) - 乱数で変化させる際、rand(d,3d)ではなく、rand(1.13d,2.87d)にした((これが1と3の場合、14.18Gになる)) - そもそもオフラインでやっているからシミュレーションと言っていいのか怪しい - [本人のツイート](https://twitter.com/5bin101/status/1469992023121924101) - [wataさんとけんしんさんのスレッド](https://twitter.com/wata_orz/status/1471340575303811075) - [けんしんさんのブログ](https://blog.knshnb.com/posts/ahc007-optuna/) - [1.14094d,3.01629d]が最適 - "実際は、モンテカルロサンプリングでの設定はすべての辺の重みがわかったオフラインの設定であり、本来求めたいオンラインでの問題設定に比べて有利になってしまっていました。 その部分の補正のためにこのような調整を入れるとスコアが良くなるようです。" ### ## DFS - [AtCoder Heuristic Contest 002(AHC002) Walking on Tiles](https://atcoder.jp/contests/ahc002/tasks/ahc002_a) assyさん(37位) - 汎用的に使えそう→"時間いっぱいDFSしても、おそらくパスの末端を沢山探索することになってスコアが伸びていないと思い、1回のDFSを100msにして、現時点でのベストのパスの途中から別の経路でDFSをやり直す。やり直す地点は、始点からパス長の8割の地点の中からランダムに選択する。" - ランダムではなく、貪欲に選んでいる - [本人の参加記](https://assy.hatenablog.jp/entry/2021/04/26/200720) - [AtCoder Heuristic Contest 011](https://atcoder.jp/contests/ahc011/tasks/ahc011_a) mtsdさん(6位) - 木の構築に乱択DFSを使っている。 - [本人の参加記](https://mtsd-programming.hatenablog.com/entry/2022/06/12/190000) - スライドパズルの部分にDPを使っていて面白かった ## 推定 ### ギブスサンプリング - [AtCoder Heuristic Contest 025](https://atcoder.jp/contests/ahc025/tasks/ahc025_a) wataさん(延長戦順位表1位) - [本人のツイート](https://twitter.com/wata_orz/status/1716033094405505107) ## 心構え(?) ### 定数倍高速化に拘りすぎない ### 時間をかける - めちゃくちゃ重要 ### TODOを管理する - 終了後にあ、これやってなかった……はよくあること。後で考えないと(やらないと)いけないところは箇条書きにしておく。