木DPと全方位木DPを基礎から抽象化まで解説【競技プログラミング】
競技プログラミングでよく出題される木DPについての説明と、木DPで解ける一部の問題を同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。
木DP基本的な考え方とイメージ木DP とは、根を一つ固 ...
半分全列挙による全探索の高速化
N 個の要素の組み合わせを計算する際、N/2 ずつの2グループに分けてそれぞれを全列挙し、組み合わせ方を高速に求めるという工夫を「半分全列挙」と言います。
選択した数列の合計値を半分全列挙で探索する場合（\(2^4\)ずつに分け ...組み合わせゲーム理論の基礎とGrundy数での勝敗判定アルゴリズム
競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。
前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題については後半にあります。
組み合わせゲーム ...区間DP の考え方と使える状況まとめ
競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。
区間DPとは区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。
基本的には、以下のような DP ...
競プロでよく出る区間和問題の解き方まとめ
区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。
一次元の区間和累積和を用いることで、
前処理：\(O(N)\)クエリ：\(O(1)\)
で処理がで ...
ビットDP(bit DP)の考え方 ~集合に対する動的計画法~
競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。
ビットDPとはビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 ...
競技プログラミングで解法を思いつくための典型的な考え方
競技プログラミングの問題を解くためには２つのステップがあります。
問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く
必要な（知っておくべき）アルゴリズムやデータ構造は色 ...
桁DP(Digit DP) を考え方から問題例まで徹底解説！
競技プログラミングで良く用いられる動的計画法の1つ「桁DP」について解説します。
桁DPとは桁ごとに分けて考える動的計画法です。
「1からNまでの整数について、条件を満たす数はいくつあるか？」「1からNまでの ...
競プロでよく使う二項係数(nCk)を素数(p)で割った余りの計算と逆元のまとめ
競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7\) の素数を使用することなどが多いです。
...