101623: [AtCoder]ABC162 D - RGB Triplets

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给你一个字符串 $S$ ,你需要找到所有满足要求的三元组 $(i,j,k)$ 。其中 $S_i \neq S_j$ , $S_j \neq S_k $ , $S_i \neq S_k$ , $j-i \neq k-j$ , $1 \le i < j < k \le N$ 。其中 $N$ 是指 $S$ 中字符的个数。输出满足条件的三元组的个数。

加入题单

上一题 下一题 算法标签: