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

---

難易度感

問題は大きく3パターンに分かれる。

1つは、有名アルゴリズムの中身を少しいじる必要があるもの。
「なんかよくわかんないけどコピペしたら動いた」でCを突破した人は詰み。

1つは、アルゴリズムを自分で考察して生み出す必要があるもの。
閃けばコード自体はB問題レベルだったりするが、閃かないと全く手が出ない。
時々、EFGを解けてるのにDを解けてない人を見かける。

1つは、数学問題。
高校時代勉強をサボってきた人は詰み。
普通の数学と違って、「ここまでは手計算で頑張って、ここから先はプログラムに任せる」という判断が必要。

D問題安定は全パターンに対応できないといけないので、かなりハードルが高い。

数学系

• エラトステネスの篩

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