7K12 blog

猫でも分かるアルゴリズム解説

ABC130 E - Common Subsequence

f:id:tkr987:20200218222711p:plain

https://atcoder.jp/contests/abc130/submissions/10200806

最初に文章を読んだ時unordered_mapでカウントするのかと思った(^^;

解説を読んだらLCS系DPだった。ということで、大前提としてLCSだと気づく必要がある。気づけなかった人は諦めよう(は?)

f:id:tkr987:20200218225548p:plain

LCSを実装するためには以下を暗記すると効率良いと思う。

  • S[x] != T[y] のとき dp[y][x] = max(dp[y-1][x], dp[y][x-1]);
  • S[x] == T[y] のとき dp[y][x] = dp[y-1][x-1] + 1;

S[x] != T[y] のとき赤同士で比較しても意味がなく、緑ブロックと赤を片方ずつ比較するのが大事な考え方になる。

f:id:tkr987:20200218230647p:plain

ただし、今回は単純な最大値でなく組み合わせの数なので、以下のように拡張する。

  • S[x] != T[y] のとき dp[y][x] += (dp[y-1][x] + dp[y][x-1] - dp[y-1][x-1]);
  • S[x] == T[y] のとき dp[y][x] += (dp[y-1][x] + dp[y][x-1] - dp[y-1][x-1] + dp[y-1][x-1]);

f:id:tkr987:20200218232123p:plain

包除原理の考え方で S[x] != T[y] のとき重複してカウントしてしまった緑ブロックの組み合わせ数を引く。S[x] == T[y] のときも基本的に同じ考え方で計算するが、ST両方の3を必ず使う組み合わせ数を追加で加算する必要がある。これは緑ブロックの組み合わせ数と一致するため、最後にdp[y-1][x-1]を加算する。

 

なお、先頭にダミー値を入れて1-indexにすると実装が楽だと思う。


 

このように暗記すると以下のLCSも同じように解ける。

Educational DP Contest F: LCS

f:id:tkr987:20200218232352p:plain

https://atcoder.jp/contests/dp/submissions/10199330

 

この問題は復元が必要になる。

これはupdateフラグと更新元座標を保存する変数を追加し、後ろから復元する。

 

ちなみに、このブログと旧ブログ合わせて100個目のプログラミング記事になった。

約1年で100個プログラミング記事を書いた計算になる。偉いな自分。

http://9871225.blog.fc2.com/blog-category-15.html