ABC214 F Substrings

公式解説は貰うDPで書かれているが, ここでは配るDPの解法を示す.

この問題は通常の部分文字列の個数を求める部分列DPを少し改善することで解くことができる. ここではけんちょんさんの部分列 DP --- 文字列の部分文字列を重複なく走査する DP の特集で説明されている部分文字列の個数を求めるDPをベースに考える.

通常の部分列DPを配るDPで解くのであれば, 次に選ぶ文字は最左のものを選ぶ. しかし今回はそこに隣り合う文字を選んではいけないという制約がある. そこで, もし次に選ぶ文字の最左のindexが今見ている文字のindexと隣り合っている場合, 次に選ぶ文字について2つ目に左のindexをとってくることでこの制約に対応することができる.

よって, この問題を$ K = 26として$ O(NK)で解くことができた.

実装例: https://atcoder.jp/contests/abc214/submissions/25082149