ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 130 E - Common Subsequence

AtCoder プログラミング競技プログラミング

E - Common Subsequence

公式解説とほとんど同じだけど、二次元累積和が出てこないようなDPで解いたので記録しておきます。

解法

記法について

数列 $S_{1}, ..., S_{N}$ を単に $S$ 、数列 $T_{1}, ..., T_{M}$ を単に $T$ と書くことにします。

与えられた数列は1-indexedで扱い、「0要素目」として空の要素を考えることにします。空部分列" $()$ "は0要素目が入っているものとみなします。

基本の考え方

いくつか微妙に違う解き方を紹介しますが、基本の考え方は同じです。それは

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうも $T_{j}$ より前で終わっているような等しい部分列の組に対して、 $S_{i} = T_{j}$ である要素をそれぞれくっ付けることによって、等しい部分列の組が新しく出来る

ということです。図で表すとこんな感じです。

f:id:betrue12:20190617232048p:plain

このような考え方を元にDPを組んでいく、という点ではどの解法も共通しています。

公式解説のDP

公式解説のDPは、もうすこし具体的に書くと以下のものを状態として定義しています。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使いちょうど $S_{i}$ で終わるような部分列と、数列 $T$ の $j$ 要素目までを使いちょうど $T_{j}$ で終わるような部分列の組で、列として等しいものの個数。

このように定義すると、もちろん $S_{i} \ne T_{j}$ のときは $dp\lbrack i \rbrack\lbrack j \rbrack = 0$ です。そして $S_{i} = T_{j}$ のときはそれより前で成立している部分列の組全てから遷移してくるため、公式解説のように二次元累積和を用いて遷移を計算できます。

この場合、答えは $\sum_{i=0}^{N}\sum_{j=0}^{M}dp\lbrack i \rbrack\lbrack j \rbrack$ になります。

ちょっとちがうDP

これとは少し違うやり方として、以下のような状態を考えることもできます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使った部分列と、数列 $T$ の $j$ 要素目までを使いちょうど $T_{j}$ で終わるような部分列の組で、列として等しいものの個数。

ここでは $T$ のほうだけに「ちょうど終わる」条件を付けています。ここで、空部分列同士のペアはそれぞれ0要素目で終わるものと見なします。

このDPテーブルを $i$ が小さいところから埋めていく遷移を考えましょう。

「貰うDP」で考えます。 $dp\lbrack i \rbrack\lbrack j \rbrack$ に遷移してくる遷移元として2通り考えられます。まずは、

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうは $T_{j}$ でちょうど終わるような部分列の組

です。その個数はまさに $dp\lbrack i-1 \rbrack\lbrack j \rbrack$ で、これは $dp\lbrack i \rbrack\lbrack j \rbrack$ にもそのまま含まれます。

それとは別に、 $S_{i} = T_{j}$ のときに限り次のようなものが考えられます。

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうも $T_{j}$ より前で終わっているような部分列の組に対して、それぞれ $S_{i}, T_{j}$ を付け足したもの

この場合の遷移元は、 $\sum_{k=0}^{j-1} dp\lbrack i-1 \rbrack\lbrack k \rbrack$ になります。「 $T_{j}$ より前で終わっている」という条件に合致するように、 $T$ のほうの添字について $j-1$ までの和を取っている形です。

これは言うなれば「一次元累積和」ですね。この和は各 $i$ について遷移を計算する際に、 $j$ を0から $M$ まで順に動かしながら順番に足していくことで管理することができます。

このDPを最後まで計算して、 $\sum_{j=0}^{M} dp\lbrack N \rbrack\lbrack j \rbrack$ が答えです。

もうちょっとちがうDP

詳しくは説明しませんが、他にも次のような状態を定義しても解くことができます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使った部分列と、数列 $T$ の $j$ 要素目までを使った部分列の組で、列として等しいものの個数。

どっちも「ちょうど終わる」という条件がなくなってますね。この場合の遷移はLCS（最長共通部分列）のDP遷移によく似たものになり、「LCSっぽく解く」と言っている人は多分これで解いていると思います。これでも解けます。

この場合は答えは $dp\lbrack N \rbrack\lbrack M \rbrack$ になります。

このように、状態の定義がちょっとずつ違うので遷移と最終的な答えがちょっとずつ違ってきます。冒頭に書いたとおり、本質的にやっていることは同じです。

ACコード

Submission #5962772 - AtCoder Beginner Contest 130

私が本番書いた解法は2番目に紹介した「一次元累積和」のものなので、そのコードリンクです。

ちょっとずつ違う解き方が色々あるぶん、解法の情報を断片的に見るとかえって混乱するかもしれません。どのように状態を定義した場合の解法なのかを区別しながら理解し、どれでもいいので1つ決めてから解いてみることをオススメします。