AtCoder Regular Contest 081：E - Don't Be a Subsequence
問題
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 の情報を保持しておくことで何によって最小の長さが求められたか復元することができる。よって rest[i] を位置 i における dp[i] を更新したときの文字としておくと rest[0] から順番に文字の情報を next[0][rest[0]] からたどっていくことで具体的な文字列を求めることができる。
イメージ図は以下の通り。
実装上で気をつけないといけないのは文字の場所の index と区間の index が登場することである。
Submission #4201955 - AtCoder Regular Contest 081
どこに着目して考察するべきだったか
まずは条件を満たす一部を求めたうえで、具体的な文字列は復元することで求めることができる。
何がバグっていたか
得た知見(典型ポイント)
- 具体的な構成をDPの復元で求める
