ABC 401-500/ABC456C - Not Adjacent - 競技プログラミング用 知識集積所

---

問題

ABC456C

必要知識

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

• 特になし

考え方

取り出す文字列の候補はN(N+1)/2通りなので、愚直にやるとTLEする。
したがって、高速化を考える必要がある。
この手の問題では、特定の位置で終わる文字列ごとにまとめて考えるのが定番。

条件を満たす文字列のうち、あるi+1文字目で終わるようなものは、以下のようなものである。

• i文字目とi+1文字目が異なる文字であれば、i文字目で終わるようなもの全てを1文字延長したもの
• i+1文字目だけのもの

つまり、カウンターを用意してから文字列を前から順に見て、

• 最初の文字か、直前と同じ文字の場合カウンターを1にリセット
• そうでない場合はカウンターを1進める

とすれば、その位置で終わる文字列の個数が即座に求められる。
よって、その値を1文字見るごとに足しこんでいけば答えが得られる。

解答例

解答例

注意点

long long型を使用するか、剰余類環の考えを用いる。

この問題は、998244353で割った余りを出すように指示がある。
この指示は通常、答えが数万桁になるような問題で使われるものであるが、このC問題では、D問題と双子問題にするためだけに存在している。

流石に候補がN(N+1)/2通り全部条件を満たすとint型からは溢れるが、long long型を使えば普通に求めて最後に剰余を1回取るだけでよい。

あるいは、やや過剰ではあるが、剰余類環の考えを用いて、足し算のたびに剰余を取ってもよい。

別解