スライドbitDP
AtCoder
AtCoder700点
ARC-E
bitDP
スライドbitDP
DP
数え上げ問題
DP状態:その状態がどこまで続くのかを添字にもつ
状態遷移を意識するDP
入力が定数個
数列
グラフ・盤面・数列の個数の数え上げ
連続部分列を扱う問題
橙色diff
bitを遷移させていくナップサックDP
ナップサックDP
5 + 7 + 5 = 17 なの、よくできてる！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…
AtCoder
AtCoder700点
DP
DP高速化
変化・遷移が限られる
区間
区間分割型ナップサックDP
回文
パリティ
DP高速化:累積和
累積和
bitDP
黄色diff
AGC-like
スライドbitDP
Zero-Sum Ranges
各アルファベットごとに考える
遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…
AtCoder
AtCoder900点
方程式
連立一次方程式
パリティ
XOR
色に関する問題
グリッド
条件の言い換え
ほとんどのところで値が一定値に決まる
DP
グラフ・盤面・数列の個数の数え上げ
ワイルドカード問題
数え上げ問題
操作
操作後の結果の数え上げ
sparseな問題
bitDP
スライドbitDP
nC2
橙色diff
ARC-like
ARC-F
面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…
AtCoder
AtCoder700点
DP
操作:隣接swap
操作:swap
操作
最小回数
ある量を固定して考える
転倒数
BIT
bitDP
パリティ
条件の言い換え
青色diff
ARC-like
DP状態:吸い出しと吸い込み
bitを遷移させていくナップサックDP
スライドbitDP
要素の並び替えを管理するDP
隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる！！！ drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…
