競技プログラマの名前で呼ばれるアルゴリズムたち

競技プログラミング Advent Calendar 2017 Day 3 の記事です．

競技プログラマが生み出した，あるいは世に普及させたすごいテクニックには，その人の名前が付けられることがあります．そのようなものを，とりあえず思いつくだけ辞書順に列挙してみました．説明は簡単にしか書かないので，詳細はリンク先を見てください．本当にそう呼んでいいのか怪しいものも含みます． $O$ 表記は特に書かれていなければ時間計算量を表します．

他にこういうのもあるよ，というのを知っている方は Twitter で教えてください．

chokudai サーチ

長時間コンテストで使うアルゴリズム．時間の管理と多様性の確保が楽なビームサーチの亜種．僕は書いたことがないけどよく見る．

http://chokudai.hatenablog.com/entry/2017/04/12/055515

colun 法

この名前は今僕が付けた．スタックメモリの制限が小さいジャッジで，スタックメモリを自分で確保したヒープメモリに付け替えることによって，スタックオーバーフローを回避する．

http://www.colun.net/archives/547

imos 法

「数列 $A$ の $A_{l}, A_{l + 1}, \dots, A_{r}$ に $x$ を足せ」という大量のクエリを一度にまとめて処理する．二次元以上の長方形領域に対するクエリにも使える．AtCoder Beginner Contest で超頻出．

https://imoz.jp/algorithms/imos_method.html

iwi 法

「データ構造をマージする一般的なテク」．

http://topcoder.g.hatena.ne.jp/iwiwi/20131226/1388062106

Kitamasa 法

数列の線形な $d$ 項間漸化式が与えられたときに $n$ 項目が知りたいとする．漸化式を行列で書いて普通に冪乗すると $O (d^{3} \log n)$ かかるところを， $O (d^{2} \log n)$ で求める．FFT を使うと $O (d \log d \log n)$ だけど，小さい制約だと定数倍で $O (d^{2} \log n)$ に負けるらしい．線形代数的にはコンパニオン行列の冪乗になるらしいけどそれに関する tmaehara 先生の資料がロストしてしまっている．

Komaki 砲

WA を大量に送りつけた後，ACすること．あるいはメモ化再帰のスタックオーバーフローを回避すること．

https://topcoder.g.hatena.ne.jp/CKomaki/20131226/1388068510

kyuridenamida 法

変な方法で AC を得ること．たぶん．具体的には，

DP が想定解の所を，枝刈り探索や焼きなまし法でがんばる
Clang の最適化パワーに祈る
- https://abc033.contest.atcoder.jp/submissions/630162
各提出ごと，テストケースごとの結果が得られるジャッジで，テストケースを特定する
- 例えば，入力のハッシュを取って $i$ 回目の提出で $i$ ビット目が立ってるかを exit(hash >> i & 1) で調べるとか

など．

Mo's Algorithm

数列に対するクエリを，先読みして適切な順番で処理することで高速化する．平方分割．

osak 法

自然数 $n$ の素因数分解を $O (\log n)$ で行う．ただし，エラトステネスを前処理として行う必要があるので，時間 $O (k \log \log k)$ ，空間 $O (k)$ の前処理が必要 ( $k$ は $n$ の最大値)．JAG 夏合宿 day 3 K のジャッジ解を作るときに教えてもらった．

http://www.osak.jp/diary/diary_201310.html#20131017

yosupo 法

木の橋を lowlink を使わずに imos 法で求める．個人的に，これ知ったとき感動した．関節点もできると Twitter で見た気がするけど該当ツイートが見つけられなかった．

https://www.slideshare.net/chokudai/arc039/44