レベル別リスト/C問題レベル - 競技プログラミング用 知識集積所

---

難易度感

おそらく競プロの最大の壁。
ここからは、与えられるデータサイズが大きく、問題文に書いてある通りにやると実行時間が爆発するものがほとんど。
ただ実行して答えが出せるだけではなく、答えが高速に出せるかどうかという問題になる。

必要な知識もほとんどが高速化に関するものである。
しかも、高速化テクニックもかなり種類が多い。
自分が知らないアルゴリズムだったらどうしようという不安に負けない精神、大事。

分岐やループ

• do-whileループ（未作成）

変数の中身次第でコードを何回も実行する。
同じような処理を何度も繰り返したい場合に。
少し特殊な挙動をするので使い道は少ないが、一部の限られた状況で活躍する。
……順列全探索（未作成）以外で使われているのを見たことがない気もする。

区間処理系

• sliding window法

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

• 尺取法

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

• 累積和

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

数学系

• 素数判定

与えられた数が素数かどうか判定するアルゴリズム。試し割り法。

• 素因数分解

与えられた数を素数の積に分解するアルゴリズム。
毎回O(n)かかるものと、前処理にO(n*loglogn)かかるがその後は毎回O(logn)ですむものがある。

• 剰余類環

答えが非常に大きくなるのでコレで割った余りだけ答えてください、という問題に答えるための知識。

その他

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

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