Problem:


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



Sample input:
4
RRGB


Sample output:
1

Submission status: Accepted

Solution code:
N = int(input())
R = [0]*N
G = [0]*N
B = [0]*N
S = input()
R_sum,G_sum,B_sum = 0,0,0
for i in range(N):
    if(S[i]=="R"):
        R_sum += 1
        R[i] = R_sum
    elif(S[i] == "G"):
        G_sum += 1
        G[i] = G_sum
    else:
        B_sum += 1
        B[i] = B_sum
ans = 0
for i in range(0,N-1):
    for j in range(i+1,N):
        if((S[i] == "R" and S[j] == "G") or (S[i] == "G" and S[j] == "R")):
            ans += B[N-1]-B[j]
            point_index = j+(j-i)
            if(point_index >= N):
                continue
            elif(S[point_index]=="B"):
                    ans -= 1
        elif((S[i] == "G" and S[j] == "B") or (S[i] == "B" and S[j] == "G")):
            ans += R[N-1]-R[j]
            point_index = j+(j-i)
            if(point_index >= N):
                continue
            elif(S[point_index]=="R"):
                    ans -= 1
        elif((S[i] == "R" and S[j] == "B") or (S[i] == "B" and S[j] == "R")):
            ans += G[N-1]-G[j]
            point_index = j+(j-i)
            if(point_index >= N):
                continue
            elif(S[point_index]=="G"):
                    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

a = {}
a['R'] = [0 for _ in range(n + 1)]
a['G'] = [0 for _ in range(n + 1)]
a['B'] = [0 for _ in range(n + 1)]

for i, si in enumerate(s):
    a['R'][i + 1] += a['R'][i]
    a['G'][i + 1] += a['G'][i]
    a['B'][i + 1] += a['B'][i]
    a[si][i + 1] += 1

ans = 0
for i, si in enumerate(s):
    if si == 'R':
        keys = ['G', 'B']
    elif si == 'G':
        keys = ['B', 'R']
    else:
        keys = ['R', 'G']
    x = a[keys[0]][-1] - a[keys[0]][i + 1]
    y = a[keys[1]][-1] - a[keys[1]][i + 1]
    ans += x * y
    for j in range(1, (n - i + 1) // 2):
        sj = s[i + j]
        sk = s[i + 2 * j]
        if sj != sk and sj in keys and sk in keys:
            ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
R = S.count("R")
G = S.count("G")
ans = R*G*(N-R-G)

for i in range(N-2):
    for j in range(i,N-1):
        k = 2*j - i
        if k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1

            
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

R_cnt = S.count("R")
G_cnt = S.count("G")
B_cnt = S.count("B")
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] != S[j] and ((2*j - i) < N):
            if S[2*j - i] != S[i] and S[2*j - i] != S[j]:
                cnt += 1

print(R_cnt*G_cnt*B_cnt-cnt)

Submission status: Accepted

Solution code:
import copy
n = int(input())
S = list(input())

table = [{}]
cnt = {'R': 0, 'G': 0, 'B': 0}
for s in S:
    cnt[s] += 1
    table.append([s, copy.deepcopy(cnt)])

RGB = set(['R', 'G', 'B'])
ans = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if table[i][0] != table[j][0]:
            kigou_set = RGB ^ set([table[i][0], table[j][0]])
            kigou = list(kigou_set)[0]
            sa = table[-1][1][kigou] - table[j][1][kigou]
            ans += sa
            l = j + (j - i)
            # print(i, j, l)
            if l <= n:
                if table[l][0] == kigou:
                    # print(table[l][1],kigou)
                    ans -= 1
                
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = " "+input()
pos = [[0 for _ in range(4000*2+10)] for _ in range(3)]
s = [0 for _ in range(3)]

for i in range(1, N+1):
    if S[i] == "R":
        pos[0][i] = 1
        s[0] += 1
    elif S[i] == "G":
        pos[1][i] = 1
        s[1] += 1 
    else:
        pos[2][i] = 1
        s[2] += 1

ans = 0
for i in range(N+1):
    if pos[0][i] == 0:
        continue
    for j in range(N+1):
        if pos[1][j] == 0:
            continue
        ans += s[2]
        if 2*i-j >= 0 and pos[2][2*i-j] == 1:
            ans -= 1
        if 2*j-i >= 0 and pos[2][2*j-i] == 1:
            ans -= 1
        if (i+j)%2 == 0 and pos[2][(i+j)//2] == 1:
            ans -= 1

print(ans)

Submission status: Accepted

Solution code:
from math import *
n = int(input())
s = input()
r = 0
b = 0
g = 0
ans = 0
for i in range(n):
	rf = s[:i].count('R')
	rb = s[i:].count('R')
	bf = s[:i].count('B')
	bb = s[i:].count('B')
	gf = s[:i].count('G')
	gb = s[i:].count('G')
	if(s[i] == 'R'):
		ans += bf*gb + bb*gf
		for j in range(i+1):
			if i+j >= n:
				break
			if(s[i-j] == 'B' and s[i+j] == 'G') or (s[i-j] == 'G' and s[i+j] == 'B'):
				ans -= 1
	elif(s[i] == 'B'):
		ans += rf*gb + rb*gf
		for j in range(i+1):
			if i+j >= n:
				break
			if(s[i-j] == 'R' and s[i+j] == 'G') or (s[i-j] == 'G' and s[i+j] == 'R'):
				ans -= 1
	else:
		ans += rf*bb + rb*bf
		for j in range(i+1):
			if i+j >= n:
				break
			if(s[i-j] == 'R' and s[i+j] == 'B') or (s[i-j] == 'B' and s[i+j] == 'R'):
				ans -= 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
rui = [[0] * (n) for i in range(3)]

if s[0] == "R":
    rui[0][0] = 1
elif s[0] == "G":
    rui[1][0] = 1
else:
    rui[2][0] = 1

for i in range(n-1):
    for j in range(3):
        rui[j][i+1] = rui[j][i]
    
    if s[i+1] == "R":
        rui[0][i+1] += 1
    elif s[i+1] == "G":
        rui[1][i+1] += 1
    else:
        rui[2][i+1] += 1

mi = 0
an = 0
for i in range(1,n-1):
    if s[i] == "R":
        x = min(i,n-1-i)
        for j in range(1,x+1):
            if (s[i+j] == "G" and s[i-j] == "B") or (s[i+j] == "B" and s[i-j] == "G"):
                mi += 1
        an += (rui[1][i-1] * (rui[2][n-1] - rui[2][i]))
        an += (rui[2][i-1] * (rui[1][n-1] - rui[1][i]))
                
    elif s[i] == "G":
        x = min(i,n-1-i)
        for j in range(1,x+1):
            if (s[i+j] == "R" and s[i-j] == "B") or (s[i+j] == "B" and s[i-j] == "R"):
                mi += 1
        an += (rui[0][i-1] * (rui[2][n-1] - rui[2][i]))
        an += (rui[2][i-1] * (rui[0][n-1] - rui[0][i]))
                
    elif s[i] == "B":
        x = min(i,n-1-i)
        for j in range(1,x+1):
            if (s[i+j] == "R" and s[i-j] == "G") or (s[i+j] == "G" and s[i-j] == "R"):
                mi += 1
        
        an += (rui[0][i-1] * (rui[1][n-1] - rui[1][i]))
        an += (rui[1][i-1] * (rui[0][n-1] - rui[0][i]))
        
print(an-mi)

Submission status: Accepted

Solution code:
from itertools import accumulate

n = int(input())
s = input()
d = {'R':1, 'G':2, 'B':3}
ss = list(map(d.get, s))
r = list(accumulate([i == 1 for i in ss]))
g = list(accumulate([i == 2 for i in ss]))
b = list(accumulate([i == 3 for i in ss]))
ans = 0
for i in range(1,n-1):
    if ss[i] == 1:
        tmp = g[i-1] * (b[-1] - b[i-1]) + b[i-1] * (g[-1] - g[i-1])
    elif ss[i] == 2:
        tmp = r[i-1] * (b[-1] - b[i-1]) + b[i-1] * (r[-1] - r[i-1])
    elif ss[i] == 3:
        tmp = r[i-1] * (g[-1] - g[i-1]) + g[i-1] * (r[-1] - r[i-1])

    ans += tmp
    # print(i, tmp, ans)

for i in range(n-2):
    for j in range(i+1, n-1):
        idx =  2*j-i
        if idx >= n:
            break
        if ss[i] != ss[j] and ss[j] != ss[idx] and ss[idx] != ss[i]:
            # print(i,j,idx, s[i], s[j], s[idx])
            ans -= 1

print(ans)

Submission status: Accepted

Solution code:

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r * g * b


for i in range(n):
    for j in range(1, n // 2 + 1):
        if i-j < 0 or i+j > n-1:
            break
        if s[i] != s[i-j] and s[i] != s[i+j] and s[i-j] != s[i+j]:
            ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
dr={}
dg={}
db={}
for i in range(N):
    if S[i]=="R":
        dr[i]=1
    elif S[i]=="G":
        dg[i]=1
    else:
        db[i]=1
lendb=len(db)
ans=0
for r in dr:
    for g in dg:
        ans+=lendb-(2*r-g in db)-(2*g-r in db)-((r+g)/2 in db)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
L=input()
Hash=defaultdict(lambda:0)
for i in L:
    Hash[i]+=1
ans=Hash['G']*Hash['R']*Hash['B']
for j in range(2*N//3+1):
    diff=j
    for i in range(N-2*diff):
        if L[i+diff]!=L[i] and L[i+2*diff]!=L[i] and L[i+2*diff]!=L[i+diff]:
            ans-=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

#i文字目以降のRGBの数
RGB = [[0]*(N+1) for i in range(3)]
for i in range(N-1,-1,-1):
    if S[i] == "R":
        RGB[0][i] = RGB[0][i+1]+1
        RGB[1][i] = RGB[1][i+1]
        RGB[2][i] = RGB[2][i+1]
    elif S[i] == "G":
        RGB[0][i] = RGB[0][i+1]
        RGB[1][i] = RGB[1][i+1]+1
        RGB[2][i] = RGB[2][i+1]
    else:
        RGB[0][i] = RGB[0][i+1]
        RGB[1][i] = RGB[1][i+1]
        RGB[2][i] = RGB[2][i+1]+1

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        if (S[i] == "R" and S[j] == "G") or (S[i] == "G" and S[j] == "R"):
            ans += RGB[2][j]
            if j+(j-i) < N and S[j+(j-i)] == "B":
                ans -= 1
        elif (S[i] == "G" and S[j] == "B") or (S[i] == "B" and S[j] == "G"):
            ans += RGB[0][j]
            if j+(j-i) < N and S[j+(j-i)] == "R":
                ans -= 1
        elif (S[i] == "R" and S[j] == "B") or (S[i] == "B" and S[j] == "R"):
            ans += RGB[1][j]
            if j+(j-i) < N and S[j+(j-i)] == "G":
                ans -= 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    r = S.count("R")
    g = S.count("G")
    b = S.count("B")

    minus = 0
    for k in range(2000):
        if k * 2 + 3 > N:
            break
        for i in range(N-k*2-2):
            if S[i] != S[i+k+1] and S[i] != S[i+2*k+2] and S[i+k+1] != S[i+2*k+2]:
                minus += 1

    print(r*g*b - minus)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()

    rcs = [0] * N
    gcs = [0] * N
    bcs = [0] * N

    for i in range(N):
        if S[i] == 'R':
            rcs[i] = 1
        elif S[i] == 'G':
            gcs[i] = 1
        elif S[i] == 'B':
            bcs[i] = 1

    for i in range(1, N):
        rcs[i] += rcs[i - 1]
        gcs[i] += gcs[i - 1]
        bcs[i] += bcs[i - 1]

    result = 0
    for i in range(N):
        if S[i] == 'R':
            for j in range(i + 1, N):
                if S[j] == 'R':
                    continue
                elif S[j] == 'G':
                    result += bcs[N - 1] - bcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'B':
                        result -= 1
                elif S[j] == 'B':
                    result += gcs[N - 1] - gcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'G':
                        result -= 1
        elif S[i] == 'G':
            for j in range(i + 1, N):
                if S[j] == 'G':
                    continue
                elif S[j] == 'R':
                    result += bcs[N - 1] - bcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'B':
                        result -= 1
                elif S[j] == 'B':
                    result += rcs[N - 1] - rcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'R':
                        result -= 1
        elif S[i] == 'B':
            for j in range(i + 1, N):
                if S[j] == 'B':
                    continue
                elif S[j] == 'R':
                    result += gcs[N - 1] - gcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'G':
                        result -= 1
                elif S[j] == 'G':
                    result += rcs[N - 1] - rcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'R':
                        result -= 1
    print(result)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
def build_dp (s) :
    temp = [0,0,0] 
    for c in s :
        if c == "R" :
            temp[0] += 1
        elif c == "G" :
            temp[1] += 1
        else :
            temp[2] += 1
    return temp

def choose3 (n) :
    return (n*(n-1)*(n-2))//6

def choose2 (n) :
    return (n*(n-1))//2

def d(n, s) :
    dp = build_dp(s)
    all_pos = choose3(n)
    for i in range(3) :
        all_pos -= choose3(dp[i])
        for j in range(3) :
            if i == j :
                continue
            all_pos -= choose2(dp[i])*dp[j]

    for i in range(n) :
        for j in range(1,n) :
            if i-j < 0 or i+j >= n :
                break 
            if s[i-j] != s[i] and s[i+j] != s[i] and s[i-j] != s[i+j] :
                all_pos -= 1
    
    return all_pos

if __name__ == "__main__" :
    n = int(input())
    s = input()
    print(d(n, s))

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())

r = [0 for _ in range(n)]
g = [0 for _ in range(n)]
b = [0 for _ in range(n)]

for i in range(len(s)):
    if s[i] == "R":
        r[i] += 1
    elif s[i] == "G":
        g[i] += 1
    else:
        b[i] += 1
        
for i in range(1,len(s)):
    r[i] += r[i - 1]
    g[i] += g[i - 1]
    b[i] += b[i - 1]

dic = {'GR': b, 'BG': r, 'BR': g}
col = {'GR': "B", 'BG': "R", 'BR': "G"}

ans = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        if s[i] != s[j]:
            used_color = "".join(sorted(list(s[i] + s[j])))
            arr = dic[used_color]
            ans += arr[-1] - arr[j]
            if j + j - i < n:
                if s[j + j - i] == col[used_color]:
                    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
r = []
g = []
b = []
for i in range(N):
    if S[i] == 'R':
        r.append(i)
    elif S[i] == 'G':
        g.append(i)
    else:
        b.append(i)
ans = 0
R = len(r)
G = len(g)
for i in range(R):
    for j in range(G):
        x = r[i]
        y = g[j]
        if x > y:
            x, y = y, x
        num = len(b)
        if 2 * x - y >= 0 and S[2 * x - y] == 'B':
            num -= 1
        if (x+y)%2 == 0 and S[(x+y)//2] == 'B':
            num -= 1
        if 2 * y - x < N and S[2 * y - x] == 'B':
            num -= 1
        ans += num
print(ans)

Submission status: Accepted

Solution code:
#create date: 2020-04-12 21:15

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    s = ns()
    r = s.count("R")
    g = s.count("G")
    b = s.count("B")
    ans = r*g*b
    for i in range(0, n-2):
        for j in range(1, (n-1)//+1):
            if i + 2*j < n:
                if len(set([s[i], s[i+j], s[i+2*j]]))==3:
                    ans -= 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    C = [[0 for i in range(3)] for j in range(N+1)]
    for i in range(N-1,-1,-1):
        if S[i] == "R":
            C[i][0] = C[i+1][0]+1
            C[i][1] = C[i+1][1]
            C[i][2] = C[i + 1][2]
        elif S[i] == "G":
            C[i][0] = C[i + 1][0]
            C[i][1] = C[i + 1][1]+1
            C[i][2] = C[i + 1][2]
        else:
            C[i][0] = C[i + 1][0]
            C[i][1] = C[i + 1][1]
            C[i][2] = C[i + 1][2]+1
    sum = 0
    # print(S)
    for i in range(N):
        for j in range(i+1,N-1):
            if S[i] == S[j]:
                continue
            k = j - i + j
            # 残りがRである場合
            if S[i] != "R" and S[j] != "R":
                sum += C[j+1][0]
                if k < N and S[k] == "R":
                    sum -=1
                # print(f"GB:{i},{j},Rp:{C[j + 1][0]}")
            if S[i] != "G" and S[j] != "G":
                sum += C[j + 1][1]
                if k < N and S[k] == "G":
                    sum -= 1
                # print(f"RB:{i},{j},Gp:{C[j + 1][1]}")
            if S[i] != "B" and S[j] != "B":
                sum += C[j + 1][2]
                if k < N and S[k] == "B":
                    sum -= 1
                # print(f"RG:{i},{j},RB:{C[j + 1][2]}")
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
srgb=input()
red=srgb.count("R")
green=srgb.count("G")
blue=n-red-green
ans=red*green*blue
counter=0
for i in range(n):
    for j in range(i+1,n):
        k=j-i+j
        if k<n:
            if srgb[i]!=srgb[j] and srgb[j]!=srgb[k] and srgb[k]!=srgb[i]:
                counter+=1
ans-=counter
print(ans)

Submission status: Accepted

Solution code:
n,s=int(input()),input()
r=[0]*n
g=[0]*n
b=[0]*n
for i in range(n):
    if s[i]=="R":
        r[i]=1
    elif s[i]=="G":
        g[i]=1
    else:
        b[i]=1
for i in range(n-1):
    r[i+1]+=r[i]
    g[i+1]+=g[i]
    b[i+1]+=b[i]
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i]!=s[j]:
            if {s[i],s[j]}=={"R","G"}:
                ans+=b[-1]-b[j]
                if 2*j-i<n and s[2*j-i]=="B":
                    ans-=1
            if {s[i],s[j]}=={"R","B"}:
                ans+=g[-1]-g[j]
                if 2*j-i<n and s[2*j-i]=="G":
                    ans-=1
            if {s[i],s[j]}=={"B","G"}:
                ans+=r[-1]-r[j]
                if 2*j-i<n and s[2*j-i]=="R":
                    ans-=1           
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    else:
        B.append(i)
#print(R, G, B, sep='\n')
Bs = set(B)
ans = 0
for r in R:
    for g in G:
        l, g = min(r, g), max(r, g)
        ans += len(B)
        ans -= (2*g - l) in Bs
        ans -= (2*l - g) in Bs
        ans -= (g + l) % 2 == 0 and (g + l)//2 in Bs
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
cnt = {
    "R": 0,
    "G": 0,
    "B": 0
}

for i, c in enumerate(s):
    cnt[c] += 1

ans = cnt["R"] * cnt["G"] * cnt["B"]
d = 0
for i in range(n-2):
    for j in range(i + 1, n - 1):
        k = j + (j - i)
        if (k < n):
            if (s[i] != s[j])and(s[j] != s[k]) and (s[k] != s[i]):
                d += 1

print(ans-d)

Submission status: Accepted

Solution code:

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

N = int(input())
S = input()

rgb = [0,0,0]
for i in range(N):
    if S[i] == 'R':
        rgb[0] += 1
    elif S[i] == 'G':
        rgb[1] += 1
    else:
        rgb[2] += 1

ans = rgb[0] * rgb[1] * rgb [2]
#print(ans)

for i in range(N):
    for j in range(1,(N-i+1)//2):
        if S[i] != S[i+j] and S[i] != S[i+2*j] and S[i+j] != S[i+2*j]:
            ans -= 1
#        print(ans,i,i+j,i+2*j)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

N = int(input())
S = list(input())

d = {s:[] for s in "RGB"}
for i, s in enumerate(S):
  d[s].append(i)
if d["R"] and d["G"] and d["B"]:
  ans = len(d["R"])*len(d["G"])*len(d["B"])
  for r in d["R"]:
    for g in d["G"]:
      M = max(r, g)
      m = r+g-M
      if M+M-m < N and S[M+(M-m)] == "B":
        ans -= 1
      if m-(M-m) >= 0 and S[m-(M-m)] == "B":
        ans -= 1
      if (M+m)%2 == 0 and S[(M+m)//2] == "B":
        ans -= 1
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
R = [0]*N
G = [0]*N
B = [0]*N
for k in range(N):
    if S[-k-1] == "R":
        R[-k-1] = 1
    elif S[-k-1] == "G":
        G[-k-1] = 1
    else:
        B[-k-1] = 1

for k in range(N-1,0,-1):
    R[k-1] += R[k]
    G[k-1] += G[k]
    B[k-1] += B[k]
R = R + [0]
G = G + [0]
B = B + [0]

ans = 0
for k in range(N):
    if S[k] == "R":
        ans += G[k+1]*B[k+1]
    elif S[k] == "G":
        ans += R[k+1]*B[k+1]
    else:
        ans += R[k+1]*G[k+1]

for k in range(1+N//2):
    l = 0
    while l+2*k < N:
        if S[l] != S[l+k] and S[l+k] != S[l+2*k] and S[l+2*k] != S[l]:
            ans -= 1
        l += 1
print(ans)

Submission status: Accepted

Solution code:
K = int(input())
S = input()
r = 0
g = 0
b = 0
for c in S:
  if c=="R":
    r+=1
  if c=="G":
    g+=1
  if c=="B":
    b+=1
    
ans = r*g*b

for i in range(1,2000):
  tail = i*2
  if tail>(K-1):
    break
  head = 0
  mid = i
  while tail<=(K-1):
    if S[head]!=S[mid] and S[tail]!=S[mid] and S[head]!=S[tail]:
      ans = ans-1
    head+=1
    mid+=1
    tail+=1
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input().strip()

locs = {}
RGB = {"R", "G", "B"}

for let in RGB:
    lc = []
    temp = 0
    for l in reversed(s):
        if l == let:
            temp += 1
        lc.append(temp)
    locs[let] = list(reversed(lc))

total = 0
for i in range(0, n - 2):
    il = s[i]
    for j in range(i + 1, n - 1):
        jl = s[j]
        if il != jl:
            left = (RGB - {il, jl}).pop()
            local = locs[left][j + 1]
            mk = j + (j - i)
            if mk < n and s[mk] == left:
                local -= 1
            total += local

print(total)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

bad_count = 0

for middle in range(1, n - 1):
	left = middle - 1
	right = middle + 1
	while left >= 0 and right < n:
		if s[middle] != s[left] and s[middle] != s[right] and s[right] != s[left]:
			bad_count += 1

#			print(left, middle, right)

		left -= 1
		right += 1

left_r = 0
left_g = 0
left_b = 0
right_r = 0
right_g = 0
right_b = 0

for c in s:
	if c == 'R':
		right_r += 1
	elif c == 'G':
		right_g += 1
	else:
		right_b += 1

good_count = 0

for c in s:
	if (c == 'R'):
		good_count += left_b * right_g
		good_count += right_b * left_g
		left_r += 1
		right_r -= 1
	elif c == 'G':
		good_count += left_r * right_b
		good_count += right_r * left_b
		left_g += 1
		right_g -= 1
	else:
		good_count += left_r * right_g
		good_count += right_r * left_g
		left_b += 1
		right_b -= 1

print(good_count - bad_count)

Submission status: Accepted

Solution code:
import collections

N = int(input())
S = input()

c = collections.Counter(S)
if 'R' in c.keys() and 'G' in c.keys() and 'B' in c.keys():
    ans = c['R'] * c['G'] * c['B']

    for i in range(N-2):
        for x in range(((N-i)-1)//2):
            if S[i] != S[i+x+1] and S[i] != S[i+2*(x+1)] and S[i+x+1] != S[i+2*(x+1)]:
                ans -= 1
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
s = list(input())

# 条件1の個数から条件2の否定となる個数を差し引いて答えとする
# 条件位置の個数
sc = Counter(s)
ans_c1 = sc['R']*sc['G']*sc['B']

# 条件2の否定
# RとBの間にGがある
r_idx = {i for i in range(n) if s[i]=='R'}
g_idx = {i for i in range(n) if s[i]=='G'}
b_idx = {i for i in range(n) if s[i]=='B'}

count = 0
for ri in r_idx:
    for gi in g_idx:
        if (ri+gi)%2==0 and (ri+gi)//2 in b_idx:
            count+=1

for ri in r_idx:
    for bi in b_idx:
        if (ri+bi)%2==0 and (ri+bi)//2 in g_idx:
            count+=1

for bi in b_idx:
    for gi in g_idx:
        if (bi+gi)%2==0 and (bi+gi)//2 in r_idx:
            count+=1

print(ans_c1-count)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

# R, G, Bの順
# [n + 10][2][2][2]
dp = [[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)] for _ in range(n+10)]

dp[0][0][0][0] = 1
for i in range(n):
    ch = s[i]
    
    for p in range(2):
        for q in range(2):
            for r in range(2):
                dp[i+1][p][q][r] = dp[i][p][q][r]

    if ch == 'R':
        dp[i+1][1][0][0] += dp[i][0][0][0]
        dp[i+1][1][1][0] += dp[i][0][1][0]
        dp[i+1][1][0][1] += dp[i][0][0][1]
        dp[i+1][1][1][1] += dp[i][0][1][1]
    elif ch == 'G':
        dp[i+1][0][1][0] += dp[i][0][0][0]
        dp[i+1][0][1][1] += dp[i][0][0][1]
        dp[i+1][1][1][0] += dp[i][1][0][0]
        dp[i+1][1][1][1] += dp[i][1][0][1]
    else:
        dp[i+1][0][0][1] += dp[i][0][0][0]
        dp[i+1][1][0][1] += dp[i][1][0][0]
        dp[i+1][0][1][1] += dp[i][0][1][0]
        dp[i+1][1][1][1] += dp[i][1][1][0]

ans = dp[n][1][1][1]

# ans = s.count('R') * s.count('G') * s.count('B')

# print(ans)

for i in range(n-2):
    for j in range(i+1, n-1):
        k = j + (j - i)
        if k >= n:
            break
        if s[i] != s[j] != s[k] != s[i]:
            ans -= 1
            # print(i,j,k)


print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
s = input()
flag = True
if len(set(s))<=2:
    print(0)
    flag = False
if flag:
    r = [i+1 for i in range(n) if s[i]=='R']
    b = [i+1 for i in range(n) if s[i]=='B']
    g = [i+1 for i in range(n) if s[i]=='G']
    minus = 0
    def cnt_cmb(a, b, c):
        cnt = 0
        set_c = set(c)
        for i in a:
            for j in b:
                if (i+j)/2 in set_c:
                    cnt += 1
        return cnt
    minus +=cnt_cmb(r, b, g)
    minus += cnt_cmb(b, g, r)
    minus += cnt_cmb(g, r, b)
    a = Counter(s)
    rslt = 1
    for value in a.values():
        rslt *= value
    print(rslt-minus)

Submission status: Accepted

Solution code:
n=int(input())
s=input()

r=s.count("R")
g=s.count("G")
b=s.count("B")
all_res=r*g*b

del_res=0
for i in range(1,n-1):
    for q in range(1,min(i,n-i-1)+1):
        #print(i,q)
        if s[i]!=s[i-q] and s[i]!=s[i+q] and s[i-q]!=s[i+q]:
            del_res+=1

print(all_res-del_res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
S = input()
C = collections.Counter(S)
R = [0] * (n+1)
G = [0] * (n+1)
B = [0] * (n+1)
for i,si in enumerate(S):
  R[i+1] += R[i]
  G[i+1] += G[i]
  B[i+1] += B[i]
  if si == "R":R[i+1] += 1
  elif si == "G":G[i+1] += 1
  else:B[i+1] += 1
for i in range(1,n-1):
  si = S[i]
  if si == "R":
    ans += G[i] * (B[n]-B[i+1]) + B[i] * (G[n]-G[i+1])
  elif si == "G":
    ans += R[i] * (B[n]-B[i+1]) + B[i] * (R[n]-R[i+1])
  else:
    ans += G[i] * (R[n]-R[i+1]) + R[i] * (G[n]-G[i+1])
#   print(ans,i,si)
# print(R,G,B,sep = "\n")
# print(ans,"debug")
# print(R[2] * (B[n]-B[2+1]))
    
for span in range(1,n):
  for i in range(n-2*span):
    if S[i] != S[i+span] and S[i+span] != S[i+span+span] and S[i+span+span] != S[i]:
      ans-=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
r = [0]*n
g = [0]*n
b = [0]*n
for i in range(n-1, -1, -1):
  if i != n-1:
    r[i] = r[i+1]
    b[i] = b[i+1]
    g[i] = g[i+1]
  if s[i] == "R":
    r[i] += 1
  if s[i] == "G":
    g[i] += 1
  if s[i] == "B":
    b[i] += 1

ans = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    if s[i] == s[j]:
      continue
    key = ["R", "G", "B"]
    key.remove(s[i])
    key.remove(s[j])
    k = key[0]
    if 2*j-i >= n:
      if k == "R":
        ans += r[j+1]
      if k == "G":
        ans += g[j+1]
      if k == "B":
        ans += b[j+1]
      continue
    if s[i] != s[2*j-i] and s[j] != s[2*j-i]:
      if k == "R":
        ans += r[j+1]-1
      if k == "G":
        ans += g[j+1]-1
      if k == "B":
        ans += b[j+1]-1
    else:
      if k == "R":
        ans += r[j+1]
      if k == "G":
        ans += g[j+1]
      if k == "B":
        ans += b[j+1]
    

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())

r = 0
g = 0
b = 0
for s in S:
    if s == 'R':
        r += 1
    elif s == 'G':
        g += 1
    else:
        b += 1
ans = r * b * g

d = 1
while True:
    if 2 * d >= N:
        break
    i = 0
    while True:
        j = i + d
        k = j + d
        if k >= N:
            break
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1
        i += 1
    d += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())
R = s.count("R")
B = s.count("B")
G = s.count("G")
ans = R*G*B
cnt = 0
for i in range(2000):
    for j in range(0, n-2*i):
        if s[j] != s[j+i] and s[j+i] != s[j+2*i] and s[j] != s[j+2*i]:
            cnt += 1
print(ans - cnt)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
s = input()
c = Counter(s)
a = c['R'] * c['G'] * c['B']

def search(l, r, a, t):
    while (r-l)>=0:
        mid = (l+r)//2
        if a[mid] == t:
            return True
        if a[mid] > t:
            r = mid-1
        if a[mid] < t:
            l = mid+1

    return False

ri = []
gi = []
bi = []

for i in range(n):
    if s[i] == "R":
        ri.append(i)
    elif s[i] == "G":
        gi.append(i)
    elif s[i] == "B":
        bi.append(i)
        
for i in range(len(gi)):
    for j in range(len(bi)):
        if search(0, len(ri)-1, ri, bi[j]-abs(gi[i]-bi[j])) or search(0, len(ri)-1, ri, gi[i]-abs(gi[i]-bi[j])):
            a -= 1
            
for i in range(len(bi)):
    for j in range(len(ri)):
        if search(0, len(gi)-1, gi, ri[j]-abs(bi[i]-ri[j])) or search(0, len(gi)-1, gi, bi[i]-abs(bi[i]-ri[j])):
            a -= 1
            
for i in range(len(ri)):
    for j in range(len(gi)):
        if search(0, len(bi)-1, bi, gi[j]-abs(ri[i]-gi[j])) or search(0, len(bi)-1, bi, ri[i]-abs(ri[i]-gi[j])):
            a -= 1
            
print(a)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r * g * b

for i in range(1, (N - 1) // 2 + 1):
    for j in range(N - i * 2):
        if S[j] != S[j+i] and S[j] != S[j+2*i] and S[j+i] != S[j+2*i]:
            ans -= 1

print(ans)