2020年4月3日動的計画法動的計画法, , テーマ記事, 競プロ, モノイド, 結合則, 木DP, 部分木, 全方位木DP, 単位元

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。

木DP基本的な考え方とイメージ

木DP とは、根を一つ固定した木について、以 ...

2020年3月31日AtCoder剰余, 動的計画法, 数え上げ, 逆元, 木DP, 部分木, 階乗

問題へのリンク

問題概要

木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。

制約\(2 \leq N \leq 1000 \)
考え方前提: ...

数学二項係数, 動的計画法, パスカルの三角形

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)

数学剰余, 二項係数, 動的計画法, Lucasの定理, 素数の剰余

Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さい場合は十分高速です。

Lucas の定理

任 ...

2020年2月22日動的計画法bit演算, 動的計画法, bitDP, DP, テーマ記事, 競プロ

競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。

ビットDPとは

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

2020年2月10日AtCoder動的計画法, 数え上げ, DP, 500点, 桁DP, 場合分け

問題へのリンク

問題概要

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

制約

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

2020年1月20日動的計画法入門, 動的計画法, DP, 競プロ, ナップサック

動的計画法とは

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

以下のような特徴がありますが、抽象的なのでここではざっと眺 ...

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

問題へのリンク

問題

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

制約 ...

2020年1月17日AtCoder剰余, 動的計画法, 400点, 数字の文字列, 桁ごと

問題へのリンク

問題

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

制約\(1 \leq |S| \leq ...