LCS (Longest Common Subsequence) によく似た DP！！ 問題へのリンク 問題概要 (意訳) 長さ の整数列 と、長さ の整数列 が与えられる。これらに以下の操作を繰り返すことで、要素数が等しくなるようにしたい。 A の要素を 1 つ選んで削除する B の要素を 1…

AtCoder ABC 185 E - Sequence Matching (水色, 500 点)

結構悩んだ！！！ 問題へのリンク 問題概要 長さ の文字列 と、長さ の文字列 が与えられる。 の連続する部分文字列 と、 の連続する部分文字列 をとったとき、 とする。 の考えられる最大値を求めよ。 制約 考えたこと 単純にそれぞれの部分文字列を探索し…

Codeforces Round #683 (Div. 1) B. Catching Cheaters (R1800)

共通部分列に関する問題！！！！！ 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…

AtCoder ABC 130 E - Common Subsequence (青色, 500 点)

面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …

AtCoder AGC 021 D - Reversed LCS (黄色, 900 点)