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

ビットDPとは

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

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

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

AtCoder最大値, 二分探索, 最小値

問題概要

問題へのリンク

風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のところにあり、1 秒経過するにつれて高度が \(S_i\) だけ増加する。

AtCoder400点, 二分探索, K番目, 2つの積

ARC037 億マス計算 の上位問題です。

問題概要

問題へのリンク

N個の整数 \(A_1, A_2, A_3, \cdots, A_n\) がある。
2つを選んでその積を \(\frac{N(N-1 ...

AtCoderDP, 500点, 桁ごと, お釣り, 硬貨

問題へのリンク

問題概要

\(1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}\) の紙幣で金銭のやり取りをする。

N 円払う時、支払うのに使う紙幣の枚数と、お釣りでもらう紙幣の ...

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

橋(bridge)とは

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

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

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

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

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

以下の ...

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

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

桁DPとは

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

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

AtCoder二項係数, 600点, 二次元, 区間和

問題へのリンク

問題概要

2次元の平面上で、以下のように関数 f(r,c) を定義する。

f(r,c) := (0,0)から(r,c)までの経路の個数

この時、以下を計算せよ。ただし、\(10^9+7 ...

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

問題へのリンク

問題概要

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

制約

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

AtCoder操作, 最大公約数, gcd, 不変量, 最大値, 500点, 約数

問題へのリンク

問題概要

N 個の整数列 \(A_1, A_2, \cdots, A_N\) に、以下の操作をK回まで行う。これら全てはある数の倍数となるが、その数の最大値を求めよ。

操作:\(A_1, A_2, ...