ARC 201-300/ARC206A - Range Replace - 競技プログラミング用 知識集積所

---

問題

ARC206A

必要知識

簡単な内容は省略

• 特になし

考え方

この手の処理では、異なるものよりも同じものの方が扱いやすい。
つまり、異なるものを数えていくより、同じものが何回かぶるかを考える方が簡単であることが多い。

まず、L=Rのものは何も起こらないので、どこを選んでも元通りの文字列になるため、これらは1まとめにしておく。
つまり、結果の初期化を「LとRを異なるところから選ぶ方法n(n-1)/2通り+同じところを選ぶ1通り」でしておく。

ここからかぶる個数を引くのだが、スタート位置ごとにわけて考える場合、

• 同じ数が1つ後ろにある場合、そこスタートの置換は全部スタートを1つ下げたやつとかぶる
• そうでない場合でも、同じ数が後ろにあると、そこの手前で終わるやつはそこで終わるやつとかぶる

が、ありえるかぶりパターンの全てである。

よって、前から1文字ずつ見ながら、初期化した値から

• 次も同じ文字の場合は、後ろにある全要素数を引く
• そうでない場合は、自分より後ろにある同じ数の個数を引く

で答えが出る。
これは、最初に何の数がどこにあるかをvector<deque※>などに入れて整理することで簡単にできる。

解答例

解答例

注意点

long long型を使う

解答がint型には収まらないことがある。

別解