競技プログラミング用 知識集積所
高速化系
最終更新:
sport_programming
-
view
区間処理系
- sliding window法(C問題レベル)
要素数nのデータのうち連続するm個のデータの何か(和、積、xor、最大値、など)の中で、条件を満たすものがあるか、または最大値や最小値を求める。
通常の方法でやれば計算回数がO(mn)になるところ、O(m+n)で済む。
通常の方法でやれば計算回数がO(mn)になるところ、O(m+n)で済む。
- 尺取法(C問題レベル)
要素数nのデータのうち連続する何個かのデータの何か(和、積、種類数など)の中で、条件を満たすものがいくつあるか、または最長区間や最短区間を求める。
通常の方法でやれば計算回数がO(n^2)になるところ、O(n)で済む。
通常の方法でやれば計算回数がO(n^2)になるところ、O(n)で済む。
- 累積和(C問題レベル)
vectorのようなデータ構造に対し、「ここからここまでの合計いくつ?」に高速に答えるためのアルゴリズム。
ただし、途中でvectorの中身は変えることはできない。
n個のデータに対しq回和を計算する場合、通常の方法でやれば計算回数がO(nq)になるところ、O(n+q)で済む。
ただし、途中でvectorの中身は変えることはできない。
n個のデータに対しq回和を計算する場合、通常の方法でやれば計算回数がO(nq)になるところ、O(n+q)で済む。
再帰系
- 動的計画法(C問題レベル)
再帰的問題、つまり「少し小さい問題の答えがわかっていれば簡単に答えが出る」というタイプの問題を高速に解くアルゴリズム。
応用の幅が広く、内容によってはE-F問題級やそれ以上に難しい問題もゴロゴロある。
応用の幅が広く、内容によってはE-F問題級やそれ以上に難しい問題もゴロゴロある。
- バックトレース(C問題レベル)
終了状態から逆再生しながら何かを調べるアルゴリズム。
終了となる状況が限られていたり、最後の状態が指定されているときに用いる。
終了となる状況が限られていたり、最後の状態が指定されているときに用いる。
その他
- エラトステネスの篩(D問題レベル)
n未満の素数を全て高速で列挙するアルゴリズム。
通常の方法でやれば計算回数がO(n√n)になるところ、O(n*loglogn)で済む。
通常の方法でやれば計算回数がO(n√n)になるところ、O(n*loglogn)で済む。
- 入出力高速化(必須ではない)
cinとcoutの動作を高速化する方法。
ただし、高速化による影響は小さく、一方で使用するリスクもある。
そのため、メリットよりデメリットの方が大きい気もするし、そもそも知らなくてもあまり問題ない気もする。
ただし、高速化による影響は小さく、一方で使用するリスクもある。
そのため、メリットよりデメリットの方が大きい気もするし、そもそも知らなくてもあまり問題ない気もする。