動的計画法bit演算, 動的計画法, bitDP, DP, テーマ記事

ビットDPとは

ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。

基本的には、以下のような DPを考えます。

\(dp\) := 部分集合 S に対して\(|S| ...

グラフグラフ, 深さ優先探索, 関節点, 切断点, , lowlink

橋(bridge)とは

無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います。

「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があることを言います ...

グラフグラフ, 深さ優先探索, 関節点, 切断点, , lowlink

関節点(Articulation Points)または切断点 (cut vertex) とは

連結グラフにおける関節点(切断点)とは、「グラフから取り除くと、グラフが非連結になってしまうような頂点」のことを言います。

以下の ...

動的計画法DP, 桁DP, テーマ記事, 競プロ

競技プログラミングで良く用いられる動的計画法の1つ「桁DP」について解説します。

桁DPとは

桁ごとに分けて考える動的計画法です。

「1からNまでの整数について、条件を満たす数はいくつあるか?」
「1からNまでの ...

動的計画法動的計画法, DP

動的計画法とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。

普通に計算すると同じ計算を何度も繰り返してしまい非効率であるようなアルゴリズムも、動的計画法を利用することで高速化 ...

貪欲法

貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。

その場での最善の手を選ぶことを繰り返す

貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いので非常に重要です。

大まか ...

数学

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。

このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られ ...

数学剰余, 二項係数, テーマ記事

競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7\) の素数を使用することなどが多いです。

...

探索順列

\(n!\)通りの全探索を行いたい時に順列が用いられます。

順列(permutation)とは、n個のものを順番に並べるのは何通りあるかを考える問題です。n個全てを区別できるなら、\(n!\)通りの並べ方があります。

探索幅優先探索, グラフ, キュー

幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。

木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状 ...