

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
, andB
.
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