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

ビットDPとは

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

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

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

AtCoder動的計画法, 数え上げ, DP, 500点, 桁DP, 場合分け

問題へのリンク

問題概要

1 以上 N 以下の整数で、0 でない数字がちょうど K 個あるものの個数を求めよ。

制約

\begin{align}
&1 \leq N \leq 10^{100} \\ ...

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

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

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

AtCoder動的計画法, bit全探索, BIT, bitDP, パリティ, 最小回数, 操作, 700点

問題へのリンク

問題

表が\(A_i\)、裏が\(B_i\)、と書かれた\(N\)枚のカードがある。「隣り合う2枚を選択して、入れ替えて裏返す」という操作をして、カードの並びが広義単調増加になる最小回数を求めよ。

制約 ...

AtCoder剰余, 動的計画法, 400点, 数字の文字列, 桁ごと

問題へのリンク

問題

一部が ? で与えられる数字の文字列 S について、13で割って5余る数で考えられる物は何通りあるか。

答えを 1e9+7 で割った余りで答えよ。

制約

$$1 \leq |S| ...