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

---

区間処理系

• 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問題レベル）

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

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

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