ABC162 D

問題文

R, G, B のみからなる、長さ $N$ の文字列 $S$ があります。

以下の $2$ つの条件をともに満たす組 $(i,j,k)(1\le i<j<k\le N)$ の数を求めてください。

• $S_i\ne S_j$ かつ $S_i\ne S_k$ かつ $S_j\ne S_k$ である
• $j-i\ne k-j$ である

制約

• $1\le N\le 4000$
• $S$ は R, G, B のみからなる、長さ $N$ の文字列である

まず一つ目の条件を満たす組の数を考える。

これはSから順番を気にせずR,G,Bを一つずつ選び、左から(i,j,k)とした場合の数と等しいので(Rの数)×(Gの数)×(Bの数)と等しい。

次にj-i=k-jの点を全て調べ、一つ目の条件を満たしている組の数を引くと求めたい答えとなる。

ステップ1がO(N)、ステップ2がO(n^2)となり十分高速。