ABC 401-500/ABC449C - Comfortable Distance - 競技プログラミング用 知識集積所

---

問題

ABC449C

必要知識

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

• sliding window法

考え方

問題で言っていることをざっくりまとめると、「L文字以上R文字以下離れたところに同じ文字がある組の数は？」である。
愚直に数えるとO(N(R-L))になるため、TLEする。

このような場合、片方を固定して数えたときの答えを高速に出す方法を考えるのが定石。
今回は見たい幅が一定なのでsliding window法が最適となる。

iかjかどちらかに着目しておいて、そのiから右にL個以上R個以下、または、そのjから左にL個以上R個以下の範囲にある各アルファベットの個数を長さ26のvectorで管理する。
着目変数を1つ動かすたびに窓を1つ動かす処理をO(1)でやるだけなので、全体でO(N)で終わる。

解答例

解答例

注意点

long long型を使う。

ほぼ全てが同じ文字で、LとRの範囲が非常に広い場合、答えがint型範囲に収まらない。

別解