スライドbitDP
いかにも JOI にありがちな添字の持ち方をする DP！ 問題へのリンク 問題概要 英小文字と英大文字からなる長さ の文字列 と、長さ の文字列 が与えられる。また 0 以上 3 以下の整数 が与えられる。 次の条件を満たす文字列 の長さの最小値を求めよ。 は、英…
5 + 7 + 5 = 17 なの、よくできてる！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…
遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…
面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…
隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる！！！ drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…
