競技プログラミング用知識集積所

ABC456D - Not Adjacent 2

最終更新：2026年05月04日 12:49

sport_programming

- view

管理者のみ編集可

問題

B以下レベルの内容は省略

C問題とは、連続で拾う必要がなくなった点が変わっている。
特定の位置で終わるものごとに考える点は共通だが、その処理はC問題ほど簡単ではなく動的計画法で高速化することになる。

すなわち、i文字目までからの取り出しで作れる文字列の個数を、末尾の文字種ごとに管理する。
すると、i+1文字目までを考えたときに、そこが'c'だったら、

'a'で終わる文字列の個数はそのまま
'b'で終わる文字列の個数はそのまま
'c'で終わる文字列の個数は、以下の4つの合計値に更新
- 'a'で終わる全ての文字列の最後に'c'を付け足したものの個数（つまり'a'で終わる文字列の個数）
- 'b'で終わる全ての文字列の最後に'c'を付け足したものの個数（つまり'b'で終わる文字列の個数）
- 'c'で終わる全ての文字列の個数そのまま
- 1（i+1文字目のみの文字列）

これは'a'や'b'の場合でも同様である。
したがって、これを用いてDPテーブルを更新していけば十分高速に末尾の文字ごとの個数が出せる。
最後まで処理した後で、末尾の文字ごとの個数を全て合計すれば答え。

答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
C問題とは異なり、答えは数万桁になるので最後に剰余を取るだけでは足りない。