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:
from sys import stdin
N = int(stdin.readline().rstrip())
S = (stdin.readline().rstrip())
r = []
g = []
b = []
cnt = 1
for i in S:
    if i == "R":
        r.append(cnt)
    elif i == "G":
        g.append(cnt)
    else:
        b.append(cnt)
    cnt += 1

ans = len(r)*len(g)*len(b)
for i in r:
    for j in range(1,4001):
        if i + j -1 >= N:
            break
        if i - j -1 < 0:
            break
            
        s1 = S[i+j-1]
        s2 = S[i-j-1]
        if s1 != "R" and s2 != "R" and (s1 != s2):
            ans -= 1
for i in g:
    for j in range(1,4001):
        if i + j - 1 >= N:
            break
        if i - j -1 < 0:
            break
            
        s1 = S[i+j-1]
        s2 = S[i-j-1]
        if s1 != "G" and s2 != "G" and (s1 != s2):
            ans -= 1
for i in b:
    for j in range(1,4001):
        if i + j - 1 >= N:
            break
        if i - j - 1 < 0:
            break
            
        s1 = S[i+j-1]
        s2 = S[i-j-1]
        if s1 != "B" and s2 != "B" and (s1 != s2):
            ans -= 1
print(ans)

Submission status: Accepted

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

R = [0] * N
G = [0] * N
B = [0] * N
SR = [0] * N
SG = [0] * N
SB = [0] * N
pr = 0
pg = 0
pb = 0
for i in range(N):
    if S[i] == "R":
        pr += 1
        SR[i] = pr
        R[i] = 1
    elif S[i] == "G":
        pg += 1
        SG[i] = pg
        G[i] = 1
    elif S[i] == "B":
        pb += 1
        SB[i] = pb
        B[i] = 1
        
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if R[i]:
            if G[j]:
                if j+(j-i) <= N-1 and B[j + (j-i)] == 1:
                    ans += SB[N-1] - SB[j] - 1
                else:
                    ans += SB[N-1] - SB[j]
            if B[j]:
                if j+(j-i) <= N-1 and G[j + (j-i)] == 1:
                    ans += SG[N-1] - SG[j] - 1
                else:
                    ans += SG[N-1] - SG[j]
        if G[i]:
            if B[j]:
                if j+(j-i) <= N-1 and R[j + (j-i)] == 1:
                    ans += SR[N-1] - SR[j] - 1
                else:
                    ans += SR[N-1] - SR[j]
            if R[j]:
                if j+(j-i) <= N-1 and B[j + (j-i)] == 1:
                    ans += SB[N-1] - SB[j] - 1
                else:
                    ans += SB[N-1] - SB[j]
        if B[i]:
            if G[j]:
                if j+(j-i) <= N-1 and R[j + (j-i)] == 1:
                    ans += SR[N-1] - SR[j] - 1
                else:
                    ans += SR[N-1] - SR[j]
            if R[j]:
                if j+(j-i) <= N-1 and G[j + (j-i)] == 1:
                    ans += SG[N-1] - SG[j] - 1
                else:
                    ans += SG[N-1] - SG[j]
print(ans)

Submission status: Accepted

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

    R, G, B = [], [], []
    for i in range(n):
        if s[i] == 'R':
            R.append(i + 1)
        elif s[i] == 'G':
            G.append(i + 1)
        else:
            B.append(i + 1)

    lb = len(B)
    RB, GB, SB = set(R), set(G), set(B)
    ans = 0

    for i in R:
        for j in G:
            ans += lb
            if j + (j - i) in SB:
                ans -= 1

    for i in G:
        for j in B:
            if j + (j - i) in RB:
                ans -= 1

    for i in B:
        for j in R:
            if j + (j - i) in GB:
                ans -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 1を満たす数
# 1,~2を満たす数を求める

# def checkone(a,b,c):
# 	if (a!=b and b!=c and c!=a):
# 		return True
# 	else:
# 		return False

def check(i,j,N): # i,j,2j-iは違ったらTrue
	# i < jは保証
				# (0 > (2*i-j) or (2*i-j) >= N or checkone(S[i], S[j], S[2*i-j])) and
              	# (0 > (2*j-i) or (2*j-i) >= N or checkone(S[i], S[j], S[2*j-i])) #and
			  	# ( ((i+j)%2!=0) or checkone(S[i], S[j], S[abs(int((i+j)/2))]))
	if (0 > (2*j-i) or (2*j-i) >= N):
		# print("out of range")
		return False
	else:
		return (S[j] != S[2*j-i] and S[2*j-i] != S[i])
		# return checkone(S[i], S[j], S[2*j-i])
# 2j-i <N
# j < (N+i)/2

n_equal = 0
for i in range(N):
	for j in range(i+1, int((N+i)/2)+1):
		if( S[i]==S[j]):
			continue
		else:
			if(check(i,j,N)==True):
				n_equal+=1
				# print(i, j, 2*j-i)
				# print(S[i],S[j],S[2*j-i])
				# print("toukankaku")

# print("n_equal=",n_equal)

n_R = S.count('R')
n_G = S.count('G')
n_B = S.count('B')

n_all = n_R*n_G*n_B
# print("n_all=",n_all)

print(n_all-n_equal)

Submission status: Accepted

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

r_total = s.count("R")
g_total = s.count("G")
b_total = s.count("B")

r_c = []
g_c = []
b_c = []

for moji in s:
  if moji == "R":
    r_total -= 1
  if moji == "G":
    g_total -= 1
  if moji == "B":
    b_total -= 1
  r_c.append(r_total)
  g_c.append(g_total)
  b_c.append(b_total)

color_dic = {"R": r_c, "G": g_c, "B": b_c}
#print(color_dic)
  
from itertools import combinations as cmb
counter = 0
RGB = set(["R", "G", "B"])
for i, j in cmb(list(range(n)), 2):
  #print(i, j, s[i], s[j])
  if s[i] != s[j]:
    rest_color = list(RGB - set([s[i], s[j]]))[0]
    #print(rest_color)
    counter += color_dic[rest_color][j]
    try:
      if s[2 * j - i] == rest_color:
        counter -= 1
    except IndexError:
      pass
print(counter)

Submission status: Accepted

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

pre = [[0 for i in xrange(3)] for j in xrange(n + 1)]

for i in xrange(n):
    for j in xrange(3): pre[i + 1][j] = pre[i][j]

    if s[i] == 'R': pre[i + 1][0] += 1
    elif s[i] == 'G': pre[i + 1][1] += 1
    else: pre[i + 1][2] += 1

collist = ['R', 'G', 'B']

ans = 0
for j in xrange(1, n):
    for k in xrange(j + 1, n):
        if s[j] == s[k]: continue
        
        it = 2
        if 'R' not in (s[j], s[k]): it = 0
        elif 'G' not in (s[j], s[k]): it = 1

        ans += pre[j][it]

        i = j + j - k

        if i >= 0:
            if s[i] == collist[it]: ans -= 1

print ans

Submission status: Accepted

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

r = S.count("R")
g = S.count("G")
b = S.count("B")
ans = r*g*b

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
R = 0
B = 0
G = 0
for i in range(N):
    if S[i] == 'R':
        R += 1
    elif S[i] == 'G':
        G += 1
    else:
        B += 1
ans = R*G*B
for i in range(N):
    for j in range(i+1,N):
        k = 2*j-i
        if k >= N:
            continue
        elif S[i]!= S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
s = input()
rl = []
gl = []
bl = []
for i in range(n):
    if s[i] == "R": rl.append(i+1)
    elif s[i] == "G": gl.append(i+1)
    else: bl.append(i+1)

ans = len(rl)*len(gl)*len(bl)

for i in rl:
    for j in gl:
        lb = len(bl)
        if (i+j)%2==0:
            index = bisect.bisect_left(bl, (i+j)//2)
            if lb>index and bl[index] == ((i+j)//2):
                ans -= 1
        if i>j:
            index = bisect.bisect_left(bl, 2*i-j)
            if lb>index and bl[index] == (2*i-j):
                ans -= 1
            if 2*j-i>0:
                index = bisect.bisect_left(bl, 2*j-i)
                if lb>index and bl[index] == (2*j-i):
                    ans -= 1
        elif i<j:
            index = bisect.bisect_left(bl, 2*j-i)
            if lb>index and bl[index] == (2*j-i):
                ans -= 1
            if 2*i-j>0:
                index = bisect.bisect_left(bl, 2*i-j)
                if lb>index and bl[index] == (2*i-j):
                    ans -= 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = input()
ans = 0
R = 0
G = 0
B = 0
for i in A:
  if i == 'R':
    R += 1
  elif i == 'G':
    G += 1
  elif i == 'B':
    B += 1
ans = R*G*B
for i in range(0,N-2):
  for j in range(i+1,N-1):
    k = 2*j -i
    if k < N:
      if A[i] != A[j] and A[j] != A[k] and A[k] != A[i]:
        ans -= 1
print(ans)

Submission status: Accepted

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

r = []
g = []
b = set()

for i in range(n):
  if s[i] == 'R':
    r.append(i + 1)
  elif s[i] == 'G':
    g.append(i + 1)
  else:
    b.add(i + 1)

summary = 0
for i in r:
  for j in g:
    min_value = min(i, j)
    max_value = max(i, j)
    count = 0
    dif = max_value - min_value
    if min_value - dif in b:
      count += 1
    if max_value + dif in b:
      count += 1
    if max_value - (dif / 2) in b:
      count += 1
    summary += len(b) - count

print(summary)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
pos = {
    "R": [],
    "G": [],
    "B": []
}
for i in range(n):
    pos[s[i]].append(i)
# count of "X" after pos i
count = {
    "R": [0] * n,
    "G": [0] * n,
    "B": [0] * n
}
for i in range(n - 2, -1, -1):
    prevC = s[i + 1]
    for c in "RGB":
        count[c][i] = count[c][i + 1]
    count[prevC][i] += 1
#print(pos)
#print(count)
ans = 0
for i in range(n):
    if s[i] == "R":
        for p in pos["G"]:
            if p > i:
                d = p - i
                ans += count["B"][p]
                if p + d < n and s[p + d] == "B":
                    ans -= 1
        for p in pos["B"]:
            if p > i:
                d = p - i
                ans += count["G"][p]
                if p + d < n and s[p + d] == "G":
                    ans -= 1

    if s[i] == "G":
        for p in pos["R"]:
            if p > i:
                d = p - i
                ans += count["B"][p]
                if p + d < n and s[p + d] == "B":
                    ans -= 1
        for p in pos["B"]:
            if p > i:
                d = p - i
                ans += count["R"][p]
                if p + d < n and s[p + d] == "R":
                    ans -= 1

    if s[i] == "B":
        for p in pos["G"]:
            if p > i:
                d = p - i
                ans += count["R"][p]
                if p + d < n and s[p + d] == "R":
                    ans -= 1
        for p in pos["R"]:
            if p > i:
                d = p - i
                ans += count["G"][p]
                if p + d < n and s[p + d] == "G":
                    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main2():
    res = 0
    n = int(input())
    s = str(input())
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue
            else:
                for k in range(j+1, n):
                    if s[i] == s[k] or s[j] == s[k]:
                        continue
                    if j - i == k - j:
                        continue
                    res += 1
    print(res)


def main():
    res = 0
    n = int(input())
    s = str(input())
    r = [i for i in range(n) if s[i] == "R"]
    g = [i for i in range(n) if s[i] == "G"]
    b = [i for i in range(n) if s[i] == "B"]

    for i in range(n):
        if s[i] == "R":
            res += sum(x > i for x in g) * sum(x > i for x in b)
        elif s[i] == "G":
            res += sum(x > i for x in r) * sum(x > i for x in b)
        elif s[i] == "B":
            res += sum(x > i for x in r) * sum(x > i for x in g)
        for j in range(i+1, n):
            k = (j-i)+j
            if k >= n:
                continue
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                res -= 1
    print(res)


def input(): return stdin.readline().rstrip()


main()

Submission status: Accepted

Solution code:
import collections
import bisect
N = int(input())
S = input()
ans = 0
table = collections.defaultdict(list)
for i, x in enumerate(S):
    table[x].append(i)
R = len(table["R"])
G = len(table["G"])
L = len(table["B"])

s = set(table["B"])

for i in range(R):
    for j in range(G):
        x = table["R"][i]
        y = table["G"][j]
        if x > y:
            x, y = y, x
        ans += L
        if 2*y - x in s:
            ans -= 1
        if 2*x - y in s:
            ans -= 1
        if (x+y) % 2 == 0 and (x+y)//2 in s:
            ans -= 1

print(ans)

Submission status: Accepted

Solution code:
import bisect

def d162(n , sli):

    ans = 0
    Rli = []
    Gli = []
    Bli = []

    for i in range(n):
        if sli[i] == "R":
            Rli.append(i)
        elif sli[i] == "G":
            Gli.append(i)
        else:
            Bli.append(i)

    Rcount = len(Rli)
    Gcount = len(Gli)
    Bcount = len(Bli)
    Rli.sort()
    Gli.sort()
    Bli.sort()

    for i in range(n - 3):
        for w in range(i + 1 , n):
            if sli[i] != sli[w]:
                k = "RGB".replace(sli[i] , "").replace(sli[w] , "")
                if k == "R":
                    ans += Rcount - bisect.bisect_right(Rli , w)
                elif k == "G":
                    ans += Gcount - bisect.bisect_right(Gli , w)
                else:
                    ans += Bcount - bisect.bisect_right(Bli , w)
                if w + w - i < n and sli[w + (w - i)] == k:
                    ans -= 1

    return ans

def main():
    n = int(input())
    sli = list(str(input()))
    print(d162(n , sli))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
S=input()
count=0
nocount=0
Rcount=0
Gcount=0
Bcount=0
for k in range(N):
    if S[k]=="R":
        Rcount+=1
    if S[k]=="G":
        Gcount+=1
Bcount = N -Rcount-Gcount
count=Rcount*Gcount*Bcount
for k in range(3,N+1):
    if k%2==1:
        for i in range(1,k-1,2):
            if S[i-1]!=S[k-1]:
                j=(i+k)//2
                if S[i-1]!=S[j-1] and S[k-1]!=S[j-1]:
                    nocount+=1
    if k%2==0:
        for i in range(2,k-1,2):
            if S[i-1]!=S[k-1]:
                j=(i+k)//2
                if S[i-1]!=S[j-1] and S[k-1]!=S[j-1]:
                    nocount+=1
print(count-nocount)

Submission status: Accepted

Solution code:
n = int(input())
S = tuple(input())
ans = 0
R = S.count('R')
G = S.count('G')
B = S.count('B')
for i in range(n):
    a = S[i]
    for j in range(i):
        b = S[j]
        if a == b:
            continue
        else:
            for d in ['R','G','B']:
                if d ==a or d == b:
                    continue
                else:
                    c = d
            if c == 'R':
                ans+=R
            elif c =='G':
                ans+=G
            else:
                ans+=B
            if (2*j-i)<0 :
                pass
            elif S[2*j-i] == c :
                ans -=1
            if (2 * i - j) >= n:
                pass
            elif S[2*i-j] ==c:
                ans -=1
            if (i+j)%2 == 0:
                if S[(i+j)//2] == c:
                    ans -=1
ans /=3
print(int(ans))

Submission status: Accepted

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

d = {'R':[],'G':[],'B':[]}
for i,c in enumerate(S):
    d[c].append(i)
ld = set(d['B'])

ans = 0
for si in d['R']:
    for sj in d['G']:
        tmp = len(ld)
        if max(si,sj) + abs(si-sj) in ld:
            tmp -= 1
        if min(si,sj) - abs(si-sj) in ld:
            tmp -= 1
        if min(si,sj) + abs(si-sj)/2 in ld:
            tmp -= 1
        ans += tmp

print(ans)

Submission status: Accepted

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

r=[]
g=[]
b=[]
for i,s in enumerate(S):
    if s=="R":
        r.append(i)
    elif s=="G":
        g.append(i)
    else:
        b.append(i)

ans=len(r)*len(g)*len(b)
for gap in range(1,(n-1)//2+1):
    i=0
    j=i+gap
    k=j+gap
    while k<=n-1:
        if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
            ans-=1
        i+=1
        j+=1
        k+=1
    
print(ans)

Submission status: Accepted

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

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

for i in range(1,n-1):
  m=min(i,n-1-i)
  for j in range(1,m+1):
    if s[i-j]!=s[i]:
      if s[i]!=s[i+j]:
        if s[i+j]!=s[i-j]:
          ans=ans-1
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    n = I()
    s = input().rstrip()

    r = [i for i, x in enumerate(s) if x == "R"]
    b = [i for i, x in enumerate(s) if x == "B"]
    g = [i for i, x in enumerate(s) if x == "G"]

    c = 0
    for d in range(1, int((n - 3) / 2) + 2):
        for i in range(n):
            tmp = i + d * 2
            if tmp == n:
                break
            if s[i] != s[i + d] and s[i + d] != s[tmp] and s[i] != s[tmp]:
                c += 1

    print(len(r) * len(b) * len(g) - c)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

if N >= 3:
    e = 0
    for i in range(N-2):
        for j in range(1, N//2+1):
            if i+2*j <= N-1:
                if S[i] != S[i+j] and S[i+j] != S[i+2*j] and S[i] != S[i+2*j]:
                    e += 1
            else:
                break
else:
    e = 0

R = S.count("R")
G = S.count("G")
B = S.count("B")

print(R*G*B-e)

Submission status: Accepted

Solution code:
from sys import stdin
import heapq
def main():

    input = stdin.readline

    N = int(input())
    S = input()[:-1]

    R_num = S.count("R")
    G_num = S.count("G")
    B_num = S.count("B")

    ans_sum = R_num*G_num*B_num

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

    print(ans_sum)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

if n == 1:
    print(0)
    exit(0)

r_count = 0
g_count = 0
b_count = 0
for idx, c in enumerate(s):
    if c == 'R':
        r_count += 1
    elif c == 'G':
        g_count += 1
    elif c == 'B':
        b_count += 1
# print(r_count, g_count, b_count)

i = 0
removed = 0
while True:
    i += 1
    if i > n // 2:
        break
    for j in range(n):
        if j + i * 2 >= n:
            break
        if s[j] != s[j + i] and s[j + i] != s[j + i * 2] and s[j] != s[j + i * 2]:
            # print(j, j + i, j + i * 2)
            removed += 1
    # print(i, removed)

print(r_count * g_count * b_count - removed)

Submission status: Accepted

Solution code:

n = int(input())
s = list(input())
cr = [0] * n
cg = [0] * n
cb = [0] * n
for i in range(n):
    if i == 0:
        if s[i] == 'R':
            cr[i] += 1
        elif s[i] == 'G':
            cg[i] += 1
        else:
            cb[i] += 1
    else:
        cr[i] = cr[i-1]
        cg[i] = cg[i-1]
        cb[i] = cb[i-1]
        if s[i] == 'R':
            cr[i] += 1
        elif s[i] == 'G':
            cg[i] += 1
        else:
            cb[i] += 1
ans = 0
for i in range(n-2):
    a = s[i]
    for j in range(i+1, n-1):
        b = s[j]
        if a == b:
            continue
        diff = j - i
        c = list({'R', 'G', 'B'} - {a, b})[0]
        if c == 'R':
            ans += cr[-1] - cr[j]
        elif c == 'G':
            ans += cg[-1] - cg[j]
        else:
            ans += cb[-1] - cb[j]
        if j + diff < n:
            if s[j + diff] == c:
                ans -= 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product as pro

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

r = [i for i in range(n) if s[i] == 'R']
g = [i for i in range(n) if s[i] == 'G']
b = [i for i in range(n) if s[i] == 'B']
cnt = len(r)*len(g)*len(b)

length = max(len(r), len(g), len(b))
if length == len(r):
    max1 = set(r)
    min1 = g
    min2 = b

if length == len(g):
    max1 = set(g)
    min1 = r
    min2 = b

if length == len(b):
    max1 = set(b)
    min1 = g
    min2 = r

for i, j in pro(min1, min2):
    if 2*j-i in max1:
        cnt -= 1
    if 2*i-j in max1:
        cnt -= 1
    if (i+j)/2 in max1:
        cnt -= 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
T = [0]*3

for i in range(N):
    if S[i] == "R":
        T[0] += 1
    elif S[i] == "G":
        T[1] += 1
    else:
        T[2] += 1
ans = T[0]*T[1]*T[2]
t = N // 2

for i in range(t):
    i = i+1
    j = 0
    while j + 2*i < N:
        if S[j] != S[j + i] and S[j] != S[j + 2*i] and S[j+i] != S[j + 2*i]:
            ans -= 1
        j += 1

print(ans)

Submission status: Accepted

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

all = s.count('R') * s.count('G') * s.count('B')
max_diff = (n - 3) // 2
for i in range(max_diff + 1):
    for j in range(n - i - i - 2):
        if s[j] != s[j + 1 + i] and s[j] != s[j + 1 + i + 1 + i] and s[j + 1 + i] != s[j + 1 + i + 1 + i]:
            all -= 1
print(all)

Submission status: Accepted

Solution code:
import math
N=int(input())
S=input()
ans=0
R=[]
G=[]
B=[]
for i,s in enumerate(S):
  if s=="R":
    R.append(i)
  elif s=="G":
    G.append(i)
  else:
    B.append(i)
ans=len(R)*len(G)*len(B)

for r in R:
  for g in G:
    if (r+g)%2==0:
      if S[(r+g)//2]=="B":
        ans-=1
    
for r in R:
  for b in B:
    if(r+b)%2==0:
      if S[(r+b)//2]=="G":
        ans-=1
    
for g in G:
  for b in B:
    if (g+b)%2==0:
      if S[(g+b)//2]=="R":
        ans-=1
    
print(ans)

Submission status: Accepted

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

    ans = 0
    ruiseki_r = [0]*N
    ruiseki_g = [0]*N
    ruiseki_b = [0]*N

    for i in range(N):
        if S[i] == "R":
            ruiseki_r[i] = ruiseki_r[i-1] + 1
            ruiseki_g[i] = ruiseki_g[i-1]
            ruiseki_b[i] = ruiseki_b[i-1]
        if S[i] == "G":
            ruiseki_r[i] = ruiseki_r[i-1]
            ruiseki_g[i] = ruiseki_g[i-1] + 1
            ruiseki_b[i] = ruiseki_b[i-1]
        if S[i] == "B":
            ruiseki_r[i] = ruiseki_r[i-1]
            ruiseki_g[i] = ruiseki_g[i-1]
            ruiseki_b[i] = ruiseki_b[i-1] + 1
    set_rg = set(["R", "G"])
    set_gb = set(["G", "B"])
    set_rb = set(["R", "B"])
    for i in range(N-2):
        Si = S[i]
        for j in range(i+1, N-1):
            Sj = S[j]
            if Si != Sj:
                Sij = set([Si, Sj])
                if len(Sij^set_rg) == 0:
                    remain_b = ruiseki_b[-1] - ruiseki_b[j]
                    if 2*j-i < N:
                        if S[2*j-i] == "B":
                            remain_b -= 1
                    ans = ans + remain_b
                if len(Sij^set_gb) == 0:
                    remain_r = ruiseki_r[-1] - ruiseki_r[j]
                    if 2*j-i < N:
                        if S[2*j-i] == "R":
                            remain_r -= 1
                    ans = ans + remain_r
                if len(Sij^set_rb) == 0:
                    remain_g = ruiseki_g[-1] - ruiseki_g[j]
                    if 2*j-i < N:
                        if S[2*j-i] == "G":
                            remain_g -= 1
                    ans = ans + remain_g
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
n = int(input())
#n, k = map(int, sys.stdin.readline().split())
s = input()
#a = list(map(int, sys.stdin.readline().split()))

def main():
    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
    z = len(b)
    for i in range(len(r)):
        for j in range(len(g)):
            d = abs(r[i] - g[j])
            e = 0
            p = min(r[i], g[j]) - d
            q = max(r[i], g[j]) + d
            if (r[i] + g[j]) % 2 == 0:
                t = int((r[i] + g[j]) / 2)
                if p >= 0:
                    if s[p] == "B":
                        e += 1
                if q < n:
                    if s[q] == "B":
                        e += 1
                if s[t] == "B":
                    e += 1
            else:
                if p >= 0:
                    if s[p] == "B":
                        e += 1
                if q < n:
                    if s[q] == "B":
                        e += 1

            ans += (z - e)

    print(ans)
            
main()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
rr=[]
gg=[]
bb=[]
for i in range(n):
  if s[i]=='R':
    rr.append(i)
  elif s[i]=='G':
    gg.append(i)
  else:
    bb.append(i)
lr=len(rr)
lg=len(gg)
lb=len(bb)
ans=lr*lg*lb
if ans==0:
  print(0)
  exit()
#print(ans,lr,lg,lb)
for xx in rr:
  for yy in gg:
    x,y=min(xx,yy),max(xx,yy)
    d=y-x
    a=x-d
    b=y+d
    if 0<=a<n and s[a]=='B':
      ans-=1
    if 0<=b<n and s[b]=='B':
      ans-=1
    if (x+y)%2==0:
      c=(x+y)//2
      if 0<=c<n and s[c]=='B':
        ans-=1



#print(rr,gg,bb)
print(ans)

Submission status: Accepted

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

R,G,B = [],[],[]

for i in range(0,N):
    char = S[i]
    if char == "R":
        R.append(i)
    elif char == "G":
        G.append(i)
    elif char == "B":
        B.append(i)

count = len(R) * len(G) * len(B)

N2 = int(N/2 + 0.5)
for i in range(0,N):
    stri = S[i]
    for j in range(0, N2):
        if i+2*j >= N:
            break
        strj = S[i+j]
        strk = S[i+2*j]
        if stri != strj and strj != strk and stri != strk:
#             print("{} {} {}".format(stri,strj,strk))
            count -= 1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()
R=[]
G=[]
B=[]
for x in S:
    if x=="R":
        R.append(1)
        G.append(0)
        B.append(0)
    elif x=="G":
        R.append(0)
        G.append(1)
        B.append(0)
    elif x=="B":
        R.append(0)
        G.append(0)
        B.append(1)

#累積和
RR=[0]
GG=[0]
BB=[0]
for r in R: RR.append(RR[-1]+r)
for g in G: GG.append(GG[-1]+g)
for b in B: BB.append(BB[-1]+b)

ans=0

for i in range(N):
    for j in range(i+1,N):
        if S[i]=="R" and S[j]=="G":
            ans+=BB[-1]-BB[j+1]
            try:
                if S[j+j-i]=="B":
                    ans-=1
            except:
                pass
        elif S[i]=="R" and S[j]=="B":
            ans+=GG[-1]-GG[j+1]
            try:
                if S[j+j-i]=="G":
                    ans-=1
            except:
                pass
        elif S[i]=="G" and S[j]=="B":
            ans+=RR[-1]-RR[j+1]
            try:
                if S[j+j-i]=="R":
                    ans-=1
            except:
                pass
        elif S[i]=="G" and S[j]=="R":
            ans+=BB[-1]-BB[j+1]
            try:
                if S[j+j-i]=="B":
                    ans-=1
            except:
                pass
        elif S[i]=="B" and S[j]=="G":
            ans+=RR[-1]-RR[j+1]
            try:
                if S[j+j-i]=="R":
                    ans-=1
            except:
                pass
        elif S[i]=="B" and S[j]=="R":
            ans+=GG[-1]-GG[j+1]
            try:
                if S[j+j-i]=="G":
                    ans-=1
            except:
                pass
print ans

Submission status: Accepted

Solution code:
N=int(input())
S=list(str(input()))
r=S.count('R')
g=S.count('G')
b=S.count('B')
count=0

for i in range(int((N-3)/2)+1):
    for k in range(N-i*2-3+1):
        if S[k]!=S[k+i+1] and S[k]!=S[k+2*i+2] and S[k+i+1]!=S[k+2*i+2]:
            count+=1
print(r*g*b-count)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    R = [0] * N
    G = [0] * N
    B = [0] * N
    rcnt = 0
    gcnt = 0
    bcnt = 0
    rgb = {
        ('R', 'G'):'B',
        ('G', 'R'):'B',
        ('R', 'B'):'G',
        ('B', 'R'):'G',
        ('G', 'B'):'R',
        ('B', 'G'):'R'
    }
    for i, s in enumerate(S):
        if s == 'R':
            rcnt += 1
        elif s == 'G':
            gcnt += 1
        elif s == 'B':
            bcnt += 1
        R[i] = rcnt
        G[i] = gcnt
        B[i] = bcnt
    # print(R, rcnt)
    # print(G, gcnt)
    # print(B, bcnt)
    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            # print('i = {}:{}, j = {}:{}'.format(i, S[i], j, S[j]), end=', ')
            if S[i] == S[j]:
                # print('S[i] == S[j] == {}'.format(S[i]))
                continue
            s = rgb[S[i], S[j]]
            if s == 'R':
                ans += rcnt - R[j]
                # print('ans += {}'.format(rcnt - R[j]))
            elif s == 'G':
                ans += gcnt - G[j]
                # print('ans += {}'.format(gcnt - G[j]))
            elif s == 'B':
                ans += bcnt - B[j]
                # print('ans += {}'.format(bcnt - B[j]))
            tn = j + (j-i)
            if tn < N and S[tn] == s:
                ans -= 1

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# def primes(n):
#     is_prime = [True] * (n + 1)
#     is_prime[0] = False
#     is_prime[1] = False
#     for i in range(2, int(n**0.5) + 1):
#         if not is_prime[i]:
#             continue
#         for j in range(i * 2, n + 1, i):
#             is_prime[j] = False
#     return [i for i in range(n + 1) if is_prime[i]]
# p = primes(4000)
# p.append(1)

n = int(input())
s = str(input())
numr = s.count("R")
numg = s.count("G")
numb = s.count("B")
ans = numr*numb*numg
for i in range(len(s)):
    if s[i] == "R":
        for j in range(len(s)):
            if s[j] == "G":
                if i<j:
                    if i+2*(j-i) < n and  s[i+2*(j-i)] == "B":
                        ans -= 1
                    if i-(j-i) >= 0 and  s[i-(j-i)] ==  "B":
                        ans -= 1
                if i>j:
                    if i-2*(i-j) >= 0 and  s[i-2*(i-j)] == "B":
                        ans -= 1
                    if i+(i-j) < n and s[i+(i-j)] ==  "B":
                        ans -= 1
                if (i+j)%2 == 0 and s[(i+j)//2] == "B":
                    ans -= 1

print(ans)