競技プログラミング用 知識集積所
ABC433C - 1122 Substring 2
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- ランレングス圧縮※（なくても、できなくはない）
考え方
条件を満たす部分文字列の中心は、必ず使われている文字が変化した瞬間である。
そこで、各「文字が新しい種類に変わったところ」について、そこを中心とした文字列をいくつ取れるか考えて合計していけばよい。
そこで、各「文字が新しい種類に変わったところ」について、そこを中心とした文字列をいくつ取れるか考えて合計していけばよい。
仮に「iがA個続く」の直後に「jがB個続く」の境目だった場合を考える。
まず、jがi+1でなかった場合は、そもそも0である。
jがi+1であった場合は、「iの最後の1個とjの最初の1個」「iの最後の2個とjの最初の2個」……という具合に、min(A,B)個作ることができる。
この計算を楽にするためには、入力を受け取ったらランレングス圧縮※をしてしまうとよい。
（なお、愚直にやっても各数を区切り探しで1回+連続数調査で左右から1回ずつ見るだけなので、十分間に合う）
まず、jがi+1でなかった場合は、そもそも0である。
jがi+1であった場合は、「iの最後の1個とjの最初の1個」「iの最後の2個とjの最初の2個」……という具合に、min(A,B)個作ることができる。
この計算を楽にするためには、入力を受け取ったらランレングス圧縮※をしてしまうとよい。
（なお、愚直にやっても各数を区切り探しで1回+連続数調査で左右から1回ずつ見るだけなので、十分間に合う）
