内容別リスト/高速化系 - 競技プログラミング用 知識集積所

---

区間処理系

• sliding window法（C問題レベル）

要素数nのデータのうち連続するm個のデータの何か（和、積、xor、最大値、など）の中で、条件を満たすものがあるか、または最大値や最小値を求める。
通常の方法でやれば計算回数がO(mn)になるところ、O(m+n)で済む。

• 尺取法（C問題レベル）

要素数nのデータのうち連続する何個かのデータの何か（和、積、種類数など）の中で、条件を満たすものがいくつあるか、または最長区間や最短区間を求める。
通常の方法でやれば計算回数がO(n^2)になるところ、O(n)で済む。

• 累積和（C問題レベル）

vectorのようなデータ構造に対し、「ここからここまでの合計いくつ？」に高速に答えるためのアルゴリズム。
ただし、途中でvectorの中身は変えることはできない。
n個のデータに対しq回和を計算する場合、通常の方法でやれば計算回数がO(nq)になるところ、O(n+q)で済む。

再帰系

• 動的計画法（C問題レベル）

再帰的問題、つまり「少し小さい問題の答えがわかっていれば簡単に答えが出る」というタイプの問題を高速に解くアルゴリズム。
応用の幅が広く、内容によってはE-F問題級やそれ以上に難しい問題もゴロゴロある。

• バックトレース（C問題レベル）

終了状態から逆再生しながら何かを調べるアルゴリズム。
終了となる状況が限られていたり、最後の状態が指定されているときに用いる。

その他

• エラトステネスの篩（D問題レベル）

n未満の素数を全て高速で列挙するアルゴリズム。
通常の方法でやれば計算回数がO(n√n)になるところ、O(n*loglogn)で済む。

• 入出力高速化（必須ではない）

cinとcoutの動作を高速化する方法。
ただし、高速化による影響は小さく、一方で使用するリスクもある。
そのため、メリットよりデメリットの方が大きい気もするし、そもそも知らなくてもあまり問題ない気もする。