競技プログラミング用 知識集積所

高速化系

最終更新:

sport_programming

- view
管理者のみ編集可


区間処理系

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

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

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

再帰系

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

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

その他

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

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

タグ:

高速化系
ウィキ募集バナー