D - RGB Triplets Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

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

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

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

制約

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

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

題意を満たす組の数を出力せよ。

入力例 1

4
RRGB

出力例 1

1

組 (1,~3,~4) だけが 2 つの条件をともに満たします。組 (2,~3,~4) は、1 つ目の条件は満たしますが 2 つ目の条件を満たさないので不適です。

入力例 2

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

出力例 2

1800

Score : 400 points

Problem Statement

We have a string S of length N consisting of R, G, and B.

Find the number of triples (i,~j,~k)~(1 \leq i < j < k \leq N) that satisfy both of the following conditions:

  • S_i \neq S_j, S_i \neq S_k, and S_j \neq S_k.
  • j - i \neq k - j.

Constraints

  • 1 \leq N \leq 4000
  • S is a string of length N consisting of R, G, and B.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of triplets in question.

Sample Input 1

4
RRGB

Sample Output 1

1

Only the triplet (1,~3,~4) satisfies both conditions. The triplet (2,~3,~4) satisfies the first condition but not the second, so it does not count.

Sample Input 2

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

Sample Output 2

1800