betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング E - Common Subsequence 公式解説とほとんど同じだけど、二次元累積和が出てこないようなDPで解いたので記録しておきます。 解法 記法について 数列 を単に 、数列 を単に と書くことにします。 与えられた数列は1-indexedで扱い、「0要素目」として空の要素を考えることにします。空部分列" "は0要素目が入っているものとみなします。 基本の考え方 いくつか微妙に違う解き方を紹介しますが、基本の考え方は同じです。それは のほうは より前で終わっていて、 のほうも より前で終わっているような等しい部分列の組に対して、 である要素をそれぞれくっ付けることによって、等しい部分列… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F06%2F17%2F231329" title="AtCoder Beginner Contest 130 E - Common Subsequence - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2019-06-17 23:13:29 rich https://betrue12.hateblo.jp/entry/2019/06/17/231329 1.0 100%