ABC 401-500/ABC455E - Unbalanced ABC Substrings - 競技プログラミング用 知識集積所

---

問題

ABC455E

必要知識

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

• 包除原理※（少し特殊な形のもの）

考え方

異なるというのは扱いにくいので、A,B,Cのうち2つ以上が同じ個数であるものの方を数えることにする。

まず、A,Bが同じ個数であるものについて考える。
愚直にやったらもちろんTLEなので、以下のように高速化する。
i文字目より前にAがNA[i]文字、BがNB[i]文字あるとする。
区間[i,j)にAとBが同じ文字数あるということは、

NA[j] - NA[i] = NB[j] - NB[i]

が成り立つということである。
これを変形すると

NA[j] - NB[j] = NA[i] - NB[i]

となるので、つまり各位置について「そこまでに出たAの文字数-Bの文字数」だけ記録しておけばよい。
すると、この長さN+1のvectorから同じ値を異なる2ヶ所から選ぶ話になるので、カウンティング※してから「同じ値の個数*(それ-1)/2」の合計を取ればよい。
カウンティング※にmap※を用いるならO(NlogN)で十分高速。

これはB,C同じ個数やC,A同じ個数についても同様。
よって、全区間の候補N(N+1)/2からこれらを引けば……と思うところだが、A,B,C全部同じ個数であるものを3回も引いてしまう。

「そこまでに出たAの文字数-Bの文字数、Bの文字数-Cの文字数」のpair※で同じものを異なる2ヶ所から、と考えることでA,B,C全部同じ個数の区間数を出し、2回分足しなおしておくことが必要。

解答例

解答例

注意点

long long型を使用する。

候補区間数は約(1/2)N^2個なので、int型からはみ出る。
N^2くらいの値が入る可能性があるところは、long long型を用いること。

別解