アドベントカレンダー2019の12/16の記事です。こんにちは、19のxxpoxxです。いつもは競技プログラミング(Atcoder:緑)やゲームの開発、部内サービスの開発などをしています。競プロは始める際に壁に当たることは少ないのですが、少しできるようになってきたあたり、つまり中級者になれそうな時に壁に当たることが多いと思います。僕も今めちゃくちゃ壁にぶつかっています...この記事では、競プロ初心者や僕のような中級者になれない人がレベルアップするために覚えておくべきアルゴリズムをまとめていきます。そもそも、競技プログラミングとはなんぞや?という人は今年の新歓ブログリレーでeiyaさんが書いた記事を読んでみましょう。対象読者この記事は以下の人を対象にしています。中級者になるためには?なにをすればいいのでしょう。わかっていたら僕はとっくに水色になっています答えはただひとつ、問題を解くことです。過去のABCの問題を解くことで、解ける問題も増えていきます。́;ω;`)競プロはただ発想力や数学力を問うものではなく、アルゴリズム力や実装力を問うものでもあるのです。なにも勉強せずにただ問題を解いたところで全ての問題が解けるようになるわけではありません。そこで、C問題やD問題を解くために必要なアルゴリズムをまとめていこうと思います!計算量などの話も少しだけ出てくるのですが、わからない方はなんか早くなるんだなと思っておいてください。けんちょんさんの記事を読んでみてください。ソースコードの例はC++、Pythonの順に載せています。DP二分探索めっちゃ有名なアルゴリズムです。以下のようなソートされた配列があったとします。a[5]=[1,2,4,7,22]この配列に22が含まれているか調べたいとき、どのようにすれば良いでしょうか。普通の人は22が要素に含まれるか、前から見ていくと思います。これをプログラムにすると、以下のようになります。print("存在する")しかし、この例の場合、処理の回数は5回となります。今回は5個の配列なので、コンピュータで実行すればすぐに結果が返ってきますが、これが1010個の要素を持つ配列だったらどうでしょうか...?そのような時に登場するのが二分探索です!先ほどの例を用いて説明します。二分探索はその名前の通り、二つに分けて目的の要素を探していくものです。先ほどの例で22を二分探索で探索するには、以下のようにします。配列の真ん中の要素、つまり4を見る。22がそれより大きいか小さいかを判断し、大きい場合は4より上の範囲、小さい場合は4より下の範囲の真ん中の要素を見る。22なら存在すると判断する。22]を見てその真ん中の要素、つまり22を見る)22がそれより大きいか小さいかを...(ry最後までとり、22ではなかったら存在しないと判断する。いうように真ん中で区切って大小を比較し、再び真ん中で区切って...と繰り返していき、一度も目的の要素を取らなかったら存在せず、取ったら存在するというように探索していきます。難しいように見えますが(真ん中の取り方とかおかしくない?と思うかもしれません)、プログラムにすると、再帰関数を用いて次のようになります。真ん中はfloor((i+j)/2)でとっていますね。j)これを用いるのは、配列にある値が含まれているのか探す場合などです。配列のある区間における要素の和をO(1)でとってこられるようにする、O(N)のアルゴリズムです。以下のような配列があったとします。a[105]=[5,4,7,12,22,⋯,4]この配列のa[3]からa[40000]までの和が、105回のループの中で必要になったとします。愚直に3から40000まで足していくのが愚直に求める方法ですが、これではTLEになってしまうでしょう。困りました...ここで現れるのが累積和というアルゴリズム(考え方?)です。内容は簡単で、予め最初の要素から各要素の合計を配列に記録しておく、というものです。上の例なら次のようになります。sum[105+1]=[0,5,9,16,28,50,⋯]これをO(N)で持っておいて、O(1)でとってくる、ということです。