LCS
LCS (Longest Common Subsequence) によく似た DP!! 問題へのリンク 問題概要 (意訳) 長さ の整数列 と、長さ の整数列 が与えられる。これらに以下の操作を繰り返すことで、要素数が等しくなるようにしたい。 A の要素を 1 つ選んで削除する B の要素を 1…
Codeforces
CodeforcesDIV1-B
CodeforcesR1800
LCS
二次元ナップサックDP
DP
文字列問題
連続部分列を扱う問題
f(i,j)をiとjとに分離する
条件の言い換え
結構悩んだ!!! 問題へのリンク 問題概要 長さ の文字列 と、長さ の文字列 が与えられる。 の連続する部分文字列 と、 の連続する部分文字列 をとったとき、 とする。 の考えられる最大値を求めよ。 制約 考えたこと 単純にそれぞれの部分文字列を探索し…
AtCoder
AtCoder500点
ABC-E
数え上げ問題
LCS
DP
文字列問題
数列
二次元ナップサックDP
ダブルカウントを防ぐ場合分けのテクニック
累積和
DP高速化
DP高速化:累積和
二次元累積和
青色diff
共通部分列に関する問題!!!!! 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…
AtCoder
AGC-D
固定する変数を入れ替えて考える
操作:盤面を予め変更する
文字列問題
回文
DP
LCS
二次元ナップサックDP
操作
操作をK回まで行える
AtCoder900点
操作後の結果の最適化問題
最大スコア
黄色diff
面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …