色変記事でも書いたように、私が一番アルゴリズムを学んだのは青になってからです。青以降の期間が競プロ歴の7割くらいなので、当たり前かもしれませんが。
水色や青あたりで、競技プログラミングで必要な知識はほぼ揃ってしまうので、そこから先は応用力の違いになってきてしまいます。
と書いてあるのですが、個人的な感覚だと青になってからの方が学んだアルゴリズムが圧倒的に多いです。ABCは茶や緑くらいの人でも理解できるアルゴリズムを組み合わせて解く問題が多いので、高度なアルゴリズムを知らなくても青になれてしまうというのはあると思います。
しかし黄色になる、あるいはそれ以降のレベルで戦うには知識が足りないことは自覚していたので、夏休みに入ってからはひたすらアルゴリズムを勉強しました。
せっかくなので自分が何を勉強したか振り返ってみたいと思います。アルゴリズムを解説できる腕はないので、参考資料のリンクを紹介しておきます。
ところでライブラリをコピペするかどうかという話がよく議論になりますね。私はコピペに否定的だったのですが、今はどちらかといえば肯定的に考えています。だってめんんどくさいじゃん遅延セグ木などのライブラリは定数倍高速化の価値がそれなりにあり、言語仕様やアルゴリズムの内容に精通しないと自力で速いコードを書くことは難しいと思うからです。また競プロで問題を解く上ではデータ構造の内部処理に詳しくなってもあまり意味がなかったりするのも理由です。
ただしライブラリを自分で書けば実装力がつきますし、オンサイトなどでコピペできない大会もありますから、いずれ自分で全て書いてみたいなあとは思っています。
それでは紹介に移ります。ダイクストラとかUnionFindとか、簡単すぎるものは除きます。アルゴリズム名などはカタカナだったりアルファベットだったりしますが、執筆者の気分です。
数学系
ユークリッドの互除法・不定方程式
拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita
mod逆元もこれでできます。非再帰実装で何が起こっているのか、正直よく分かっていません…。
FFT/NTT
FFT（高速フーリエ変換）を完全に理解する話 - Qiita
畳み込みで殴るの最高！
…FFTは数式だけは辛うじて追えているものの、なぜ畳み込みができるのかという本質部分についてはあまり理解できていません。今のところ「離散フーリエ変換をごちゃごちゃすると、たまたま畳み込みの形に帰着されるからできる」みたいな認識で終わってます。
NTTについては完全未履修で、ライブラリだけ持ってます…（おい）
エラトステネスの篩 / osa_k法
osa_k法、「おさ・けーほう」って読んでるけどいいんでしょうか。エラトステネスの篩なんて小学生の頃から知ってるわ…と思って軽視していたのですが、osa_kはABC177E-Coprimeの解説を見て初めて知りました。(当時は素数列挙してその中で試し割り、という冷や汗解法で通しました)
Floor sum
サーバル「ALPC C『floor sum』を解いたよ。問題は、「直線 y=(Ax+B)/Mの下にある格子点の個数を求めよ」になるよ。境界を含むか含まないかには注意してね。後で話を簡単にするために左右を反転して考えることにしておくよ」 pic.twitter.com/fZvOZyOWPu— 競技プログラミングをするフレンズ (@kyopro_friends) 2020年9月10日
サーバル「1回の操作での計算がO(1)だから、全体でもlogオーダーで解けるね。AGC A300点とか、ABCのDかEくらいにそのまま出てきそうな問題だけど、ライブラリにするほど頻出なのかなー？」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2020年9月10日
ACLに入ってて、なにこれとなりました。普通にあたまいい。ABC-Eに出たら「は？」って言いながらググります。
幾何
幾何テンプレート(Geometry) | Luzhiled’s memo
Luzhiled's memoは神。Luzhiledってなんて読むのか分からないけど。Counter Clockwise (CCW) 関数を設けるのがコツで、点の位置関係の把握に困りにくくなるみたいです。
最近点対とかは普通に難しいので、個別に調べました。（最近点対についてはwikipediaが分かりやすかったです）
写像12相
「写像12相」を総整理！ 〜 数え上げ問題の学びの宝庫 〜 - Qiita
安心と信頼のけんちょんさんクオリティ。AOJで全部verifyできます。
こうして見ると、単純な数え上げ問題でも知らないことってたくさんあるんだなーと感じました。
離散対数・平方剰余
整数論pdfにあるやつです。難しい…。
ミラー・ラビン素数判定法 / ρ法
「え？これってO(√N)じゃないの？」ってなるやつです。なんか良く分かんねえけどすげええええ！！！！！
余談ですが、この前のACLコン1-BではO(√N)が間に合わないと勘違いをして、このライブラリを貼っちゃいました。
グラフ
最大流（Dinic）/ 二部マッチング / 燃やす埋める
これとFord-Fulkerson法がよく紹介されているのですが、DinicがあればFord-Fulkersonって要らないよね？と信じています。間違っていたらどなたか教えて頂きたいです。
Dinicは基本的に計算量がO(E*V^2)で、二部グラフだったり辺の容量が全て同一だったりする場合はO(E√V)、という説明がよくありますし、大半の問題はそれに合わせて作られています。ただ実際投げてみると最悪ケースで10^8付近になるかな？という場合でも余裕で間に合ったりするので、アルゴリズムの説明でよく言われる「ただし、ほとんどの場合でさらに高速に動作する」という文言は結構信頼できる気がしています。
燃やす埋めるに関しては、友達に貰ったライブラリで勉強しました。辺の張り方は落ち着いてやらないと間違えるので、あらかじめライブラリの形で持っておくのが良いと思います。
木の直径
D - 高橋くんと木の直径：解説スライドにアルゴリズムの説明があります。
実はこれ青になってから初めて知りました。アルゴリズムもダイクストラ2回で終わるから楽ちん。
木構造の問題で、直径を伸ばして考えると答えにすんなり辿り着くことは結構よくある印象です。
Lowest Common Ancestor (LCA)
ダブリングです。オイラーツアーはさわりくらいしか知りません。
強連結成分分解
アルゴリズムが胡散臭いランキング1位（個人の感想）です。有向グラフの到達可能性を調べる際は便利だったり。でも使わなくても意外に解けちゃったりします。
セグ木系
Binary Indexed Tree (BIT, Fenwick Tree)
セグ木は水色で勉強しましたが、BITは青になるまで使ったことがなかったです。区間和くらいでしか使えないけど、実装軽くて嬉しい！
区間加算点取得・区間加算区間取得も上のリンクを参考に作りました。
非再帰非２冪抽象化遅延伝播セグ木
Segment Tree のお勉強(1) | maspyのHP
Segment Tree のお勉強(2) | maspyのHP
遅延セグ木、載せられる条件も含めて難しい…。解説記事を書こうとしたこともありましたが、他の方より良く説明できる自信がなく、断念しました。
maspyさんの記事にある図が分かりやすいので、それをじっくり眺めるのがおすすめです。
２冪にした方が二分探索しやすいという説があり、ライブラリを書き換えるか迷っています。でもACLあるからいっか。
文字列
Rolling Hash
蟻本片手に学ぶアルゴリズム ~ローリングハッシュ~ - Qiita
安全で爆速なRollingHashの話 - Qiita：この記事めちゃくちゃ引用されてる印象があります。分かりやすい。
衝突回避のために以前はハッシュを2~3個tupleにして持っていたので面倒な印象でしたが、mod(2^61-1)のものを作ってからは一躍文字列問題の主力選手に。しかしこれでも基数が小さすぎると普通に衝突します（１敗）。基数は10000以上にしましょう。またそもそも文字列ごとに基数をランダムで変えてたりすると一致判定として全く意味をなさないです（１敗）。
Z-algorithm
配列解析アルゴリズム特論文字列探索・比較（１）- 東京大学医科学研究所ヒトゲノム解析センター（兼）情報理工学系研究科コンピュータ科学専攻
：ゲノム解析をしている研究室で使われたpdfのようです。文字列アルゴリズムってそういうところで使えるんですねなるほど。
マジでこれ頭いいですよね。計算結果をうまく使い回すと部分連続文字列が接頭辞とどのくらい一致しているのかが線形で全部判定できるんですね～。
色んなサイトを見て首を傾げた後で上のリンクにたどり着き、全貌を理解したときは感動しました。
その他テクニックなど
集合とその部分集合をO(3^N)で列挙するbitDP
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary
これはO(4^N)でしかできないと思ってましたが、遷移式を工夫するとO(3^N)になるみたいです。N==15くらいの問題は割とこれだったりします。
包除原理・高速ゼータ変換・高速メビウス変換
包除原理-解ける数え上げの範囲を広げよう：高速ゼータ変換・高速メビウス変換も載っています。
FFTが難解だったこともあり高速ゼータ変換の勉強をこれまで避けていたのですが、コードを見てみると数行しかなくて拍子抜けしました。N==20くらいでO(3^N)も厳しかったらこれのことが多いです。（制約エスパー、楽しい！）
Sliding Window Aggragation (SWAG)
Sliding Window Aggregation - data-structures
区間集合 [L_i, R_i) (i = 0, 1, 2, ... ) が L_i <= L_(i+1) && R_i <= R_(i+1)を満たしていて、かつ区間に対する演算が結合則を満たすとき、これを使うと線型時間で区間クエリを処理できます。特に全部の区間の幅が一定の時は左端でソートすればこれが使えます。ただこれ最悪セグ木に載せればO(NlogN)になるんですよね。定数倍がきついときにどうぞ。
入力マクロ
宣言と入力を同時に行うマクロです。超便利です。宣言だけして入力を忘れるおっちょこちょいさん（私など）におすすめ。
デバッグマクロ
printデバッグって提出前に出力部分を消さないといけないし、コンテナの中身を見るにはループを回して要素を取り出していかないといけないからめんどくさい。
そんな悩みを解消するのがデバッグマクロです。#ifdef LOCALを付けることで自分の環境でのみデバッグ出力されるようになります。つまりマクロ部分を消さなくても、AtCoder上ではデバッグ出力が表示されません！
このマクロについては個人的に色々工夫したので別記事で紹介するかもしれません。
以上です！本当は「これから学びたいアルゴリズム」の欄も作るつもりだったのですが、意外に長くなったのでここで一旦終わろうかと思います。もし書くとしたら別記事に書きます。
