d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 問題 https://atcoder.jp/contests/arc081/tasks/arc081_c 考え方 基本的な考え方は放送解説がわかりやすい。 dp[i] := 位置 i 以降で条件を満たす最小の文字列の長さ とする。そのとき dp[i] = min(dp[next[i][j]] + 1) となる。next[i][j] は 位置 i 以降で文字 c が現れる一番最初の位置の index である。 文字列の長さが求まったら、具体的に dp[0] の長さの文字列を構成することになる。これは、dp[i] の長さを求める過程で最小の長さになったときの文字 c の情報を保持しておくことで何に… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2019%2F02%2F09%2F173018" title="AtCoder Regular Contest 081：E - Don&#39;t Be a Subsequence - 数学/競プロメモ" 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-ak.f.st-hatena.com/images/fotolife/d/d_tutuz/20190209/20190209172225.png Hatena Blog https://hatena.blog 2019-02-09 17:30:18 rich https://tutuz.hateblo.jp/entry/2019/02/09/173018 1.0 100%