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: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
s = input()

r = []
g = []
b = []
for i in range(n):
    if s[i] == "R":
        r.append(i)
    if s[i] == "G":
        g.append(i)
    if s[i] == "B":
        b.append(i)

l = []
for i in range(len(r)):
    for j in range(len(g)):
        for k in range(len(b)):
            l.append([r[i],g[j],b[k]])

ans = len(l)
for i in range(len(l)):
    ll = sorted(l[i])
    if ll[1] - ll[0] == ll[2] - ll[1]:
        ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
d = {
    'R': [],
    'G': [],
    'B': []
}
for i, s in enumerate(S):
    d[s].append(i)

answer = 0
for r in d['R']:
    for g in d['G']:
        for b in d['B']:
            s = sorted([r, g, b], reverse=True)
            if s[0] - s[1] != s[1] - s[2]:
                answer += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
List_R,List_G,List_B = [],[],[]
for i,j in enumerate(S):
  if j == 'R':
    List_R.append(i+1)
  elif j == 'G':
    List_G.append(i+1)
  else:
    List_B.append(i+1)
count = 0
for i in List_R:
  for j in List_G:
    for k in List_B:
      aa = [i,j,k]
      aa.sort()
      if aa[2]-aa[1] != aa[1]-aa[0]:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

score = 0

for i in range(1,n-1):
    if s[i] == 'R':

        g = 0
        g_l = []
        for j in range(i):
            if s[j] == 'G':
                g += 1
                g_l.append(i-j)
        b = 0         
        b_l = []
        for j in range(i,n):
            if s[j] == 'B':
                b += 1
                b_l.append(j-i)
                
        common = set(g_l) & set(b_l)
        score += b*g - len(common)

for i in range(1,n-1):
    if s[i] == 'R':

        g = 0
        g_l = []
        for j in range(i):
            if s[j] == 'B':
                g += 1
                g_l.append(i-j)
        b = 0         
        b_l = []
        for j in range(i,n):
            if s[j] == 'G':
                b += 1
                b_l.append(j-i)
                
        common = set(g_l) & set(b_l)
        score += b*g - len(common)

for i in range(1,n-1):
    if s[i] == 'G':

        g = 0
        g_l = []
        for j in range(i):
            if s[j] == 'R':
                g += 1
                g_l.append(i-j)
        b = 0         
        b_l = []
        for j in range(i,n):
            if s[j] == 'B':
                b += 1
                b_l.append(j-i)
                
        common = set(g_l) & set(b_l)
        score += b*g - len(common)

for i in range(1,n-1):
    if s[i] == 'G':

        g = 0
        g_l = []
        for j in range(i):
            if s[j] == 'B':
                g += 1
                g_l.append(i-j)
        b = 0         
        b_l = []
        for j in range(i,n):
            if s[j] == 'R':
                b += 1
                b_l.append(j-i)
                
        common = set(g_l) & set(b_l)
        score += b*g - len(common)

for i in range(1,n-1):
    if s[i] == 'B':

        g = 0
        g_l = []
        for j in range(i):
            if s[j] == 'R':
                g += 1
                g_l.append(i-j)
        b = 0         
        b_l = []
        for j in range(i,n):
            if s[j] == 'G':
                b += 1
                b_l.append(j-i)
                
        common = set(g_l) & set(b_l)
        score += b*g - len(common)

for i in range(1,n-1):
    if s[i] == 'B':

        g = 0
        g_l = []
        for j in range(i):
            if s[j] == 'G':
                g += 1
                g_l.append(i-j)
        b = 0         
        b_l = []
        for j in range(i,n):
            if s[j] == 'R':
                b += 1
                b_l.append(j-i)
                
        common = set(g_l) & set(b_l)
        score += b*g - len(common)
        
print(score)

Submission status: Time Limit Exceeded

Solution code:

from bisect import bisect_left

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

d = {"R": [], "G": [], "B": []}
for i in range(N):
    d[S[i]].append(i)

ctr = {}
for v in "RGB":
    ctr[v] = len(d[v])

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] == S[j]:
            continue

        # j > k
        res = (set("RGB") - set([S[i], S[j]])).pop()
        k = bisect_left(d[res], j)

        # Find k == 2*j - i
        k0 = bisect_left(d[res], 2 * j - i)
        if k0 < ctr[res]:
            flag = int(d[res][k0] + 1 == 2 * (j + 1) - i - 1)
        else:
            flag = 0

        # Add
        ans += ctr[res] - k - flag

print(ans)

Submission status: Time Limit Exceeded

Solution code:

from bisect import bisect_left

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

d = {"R": [], "G": [], "B": []}
for i in range(N):
    d[S[i]].append(i)

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] == S[j]:
            continue

        # j > k
        res = (set("RGB") - set([S[i], S[j]])).pop()
        k = bisect_left(d[res], j)

        # Find k == 2*j - i
        k0 = bisect_left(d[res], 2 * j - i)
        if k0 < len(d[res]):
            flag = int(d[res][k0] + 1 == 2 * (j + 1) - i - 1)
        else:
            flag = 0

        # Add
        ans += len(d[res]) - k - flag

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import itertools
n=int(input())
rgb=list(input())
rgb_counter=Counter(rgb)
n_list=[i for i in range(1,n+1)]
count=0
for i,j in itertools.combinations(n_list,2):
    k=2*j-i
    if k<=n and rgb[j-1]!=rgb[i-1] and rgb[j-1]!=rgb[k-1] and rgb[i-1]!=rgb[k-1]:
        count+=1
print(rgb_counter["R"]*rgb_counter["G"]*rgb_counter["B"]-count)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1, n):
    for j in range(i + 1, n + 1):
        if s[i - 1] == "R" and s[j - 1] == "G" or s[i - 1] == "G" and s[j - 1] == "R":
            if 2 * (j - 1) - (i - 1) < n:
                if s[2 * (j - 1) - (i - 1)] == "B":
                    ans -= 1
            ans += s[j:].count("B")
        elif s[i - 1] == "G" and s[j - 1] == "B" or s[i - 1] == "B" and s[j - 1] == "G":
            if 2 * (j - 1) - (i - 1) < n:
                if s[2 * (j - 1) - (i - 1)] == "R":
                    ans -= 1
            ans += s[j:].count("R")
        elif s[i - 1] == "B" and s[j - 1] == "R" or s[i - 1] == "R" and s[j - 1] == "B":
            if 2 * (j - 1) - (i - 1) < n:
                if s[2 * (j - 1) - (i - 1)] == "G":
                    ans -= 1
            ans += s[j:].count("G")
print(ans)

Submission status: Time Limit Exceeded

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(i+1,N):
    for k in range(j+1,N):
      if k>2*j-i:
        break
      if S[i]!=S[j]!=S[k]!=S[i]:
        if j-i==k-j:
          ans -= 1

print(ans)

Submission status: Time Limit Exceeded

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(i+1,N):
    for k in range(j+1,N):
      if S[i]!=S[j]!=S[k]!=S[i]:
        if j-i==k-j:
          ans -= 1

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
  if S[i]=='R':
    for j in range(i+1,N):
      if S[j]=='G':
        ans += S[j+1:].count('B')
        if 2*j-i<=N-1 and S[2*j-i]=='B':
          ans -= 1
      if S[j]=='B':
        ans += S[j+1:].count('G')
        if 2*j-i<=N-1 and S[2*j-i]=='G':
          ans -= 1
  if S[i]=='G':
    for j in range(i+1,N):
      if S[j]=='R':
        ans += S[j+1:].count('B')
        if 2*j-i<=N-1 and S[2*j-i]=='B':
          ans -= 1
      if S[j]=='B':
        ans += S[j+1:].count('R')
        if 2*j-i<=N-1 and S[2*j-i]=='R':
          ans -= 1
  if S[i]=='B':
    for j in range(i+1,N):
      if S[j]=='G':
        ans += S[j+1:].count('R')
        if 2*j-i<=N-1 and S[2*j-i]=='R':
          ans -= 1
      if S[j]=='R':
        ans += S[j+1:].count('G')
        if 2*j-i<=N-1 and S[2*j-i]=='G':
          ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input());s=[*input()];count=0
for i in range(n):
  for j in range(i,n):
    for k in range(j,n):
      if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k] and j-i != k-j:
        count+=1
print(count)

Submission status: Time Limit Exceeded

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

from itertools import combinations as comb
count = 0
for a in comb(range(1,n+1),3):
  i = a[0] - 1
  j = a[1] - 1
  k = a[2] - 1
  if j-i == k-j:
    continue
  if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
    count += 1
print(count)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if s[i] != s[j] and s[j] != s[k] and s[i] != s[k] and (j - i) != (k - j):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if s[i] != s[j] and s[j] != s[k] and s[i] != s[k] and (j - i) != (k - j):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

rn=s.count('R')
gn=s.count('G')
bn=n-rn-gn

ans=bn*gn*rn
if n>2:
  
  for x in range(n-2):
    
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)

Submission status: Time Limit Exceeded

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

rn=s.count('R')
gn=s.count('G')
bn=n-rn-gn

ans=bn*gn*rn
if n>2:
  
  for x in range(n-2):
    
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)

Submission status: Time Limit Exceeded

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

rn=s.count('R')
gn=s.count('G')
bn=n-rn-gn

ans=0
if n>2:
  
  for x in range(n-2):
    if s[x]=='R':
      rn-=1
      ans+=gn*bn
    elif s[x]=='G':
      gn-=1
      ans+=rn*bn
    else:
      bn-=1
      ans+=gn*rn
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)

Submission status: Time Limit Exceeded

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

rn=s.count('R')
gn=s.count('G')
bn=s.count('B')

ll=len(s)
ans=0
if ll>2:
  
  for x in range(len(s)-2):
    if s[x]=='R':
      rn-=1
      ans+=gn*bn
    elif s[x]=='G':
      gn-=1
      ans+=rn*bn
    else:
      bn-=1
      ans+=gn*rn
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
rs = [0]*n
gs = [0]*n
bs = [0]*n
for i in reversed(range(n)):
    if s[i] == 'R':
        rs[i] += 1
    elif s[i] == 'G':
        gs[i] += 1
    else:
        bs[i] += 1
for i in reversed(range(n-1)):
    rs[i] += rs[i+1]
    gs[i] += gs[i+1]
    bs[i] += bs[i+1]
res = 0
for i in range(n):
    for j in range(i+1,n-1):
        if s[i] == s[j]:
            continue
        if s[i]!='B' and s[j]!='B':
            res += bs[j+1]
            if j-i+j < n:
                if s[j-i+j] == 'B':
                    res -=1
        elif s[i]!='G' and s[j]!='G':
            res += gs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'G':
                    res -=1
        else:
            res += rs[j+1]
            if j - i + j < n:
                if s[j-i+j] == 'R':
                    res -= 1
print(res)

Submission status: Time Limit Exceeded

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

RGBlist = [[S.count('R')],[S.count('G')],[S.count('B')]]


for i in range(1,N):
    RGBlist[0].append(RGBlist[0][-1] - (S[i-1] == 'R'))
    RGBlist[1].append(RGBlist[1][-1] - (S[i-1] == 'G'))
    RGBlist[2].append(RGBlist[2][-1] - (S[i-1] == 'B'))

for i in range(N-2):
    si = S[i]
    
    for j in range(i+1,N-1):
        sj = S[j]
        if si==sj:
            continue
        else:
            RGB = set(['R','G','B'])
            RGB -= set([si,sj])
            k=j+1
            kji=j-i
            if RGB == {'R'}:
                rgb = 0
            elif RGB =={'G'}:
                rgb = 1
            else:
                rgb = 2
            if k+kji-1 < len(S):
                count += RGBlist[rgb][k] - ({S[k+kji-1]} == RGB)
            else:
                count += RGBlist[rgb][k]
            
print(count)

Submission status: Time Limit Exceeded

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

for i in range(N-2):
    si = S[i]
    

    for j in range(i+1,N-1):
        sj = S[j]
        if si==sj:
            continue
        else:
            RGB = set(['R','G','B'])
            RGB -= set([si,sj])
            k=j+1
            kji=j-i
            count += (S[k : k + kji-1]+S[k+kji:]).count(*RGB)
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ans=0
for i in range(n-2):
    for j in range(i,n-1):
        for k in range(j,n):
            if s[i]==s[j] or s[j]==s[k] or s[k]==s[i]:
                continue
            if j-i == k-j :
                continue
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
out = 0
ls = []
RGB = ['R','G','B']
for i in RGB:
    ls.append([j for j, x in enumerate(S) if x == i])


# flg = [[[0 for i in range(N)] for j in range(N)] for k in range(N)]
for i in ls[0]:
    for j in ls[1]:
        for k in ls[2]:
            tmp = [i,j,k]
            tmp.sort()
            [l,m,n] = tmp
            if m-l != n-m:
                out += 1

print(out)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
out = 0
for i in range(0,N):
    for j in range(i,N):
        for k in range(j,N):
            if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                if j-i != k-j:
                    out+=1;

print(out)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import combinations as cmb

N = int(input())
S = input()
ans = 0
if N >= 3:    
    for idx in list(cmb(range(N), 3)):
        a,b,c = idx[0],idx[1],idx[2]
        if b-a != c-b and S[a] != S[b] and S[a] != S[c] and S[b] != S[c]:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
cnt = s.count('R') * s.count('G') * s.count('B')
for i in range(n - 1):
  for j in range(i + 1, n):
    try:
      if len(set([s[i], s[j], s[2 * j - i]])) == 3:
        cnt -= 1
    except IndexError:
      pass
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
s = input()
itr = itertools.combinations(range(n), 3)
cnt = 0
for tpl in itr:
  if (tpl[2] - tpl[1] != tpl[1] - tpl[0] and 
      len(set([s[tpl[0]], s[tpl[1]], s[tpl[2]]])) == 3):
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
c = list(input())

deta = list(range(n))
r = c.count("R")
g = c.count("G")
b = c.count("B")

ans = r*g*b

count  = 0

sub1 = 0

for i in range(n):
    for j in range(i,n):
        if 2*j-i<n and 2*j-i>0:
            if c[2*j-i] != c[i] and c[i] != c[j] and c[2*j-i] != c[j]:
                sub1 += 1


print(ans-sub1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
c = list(input())

deta = list(range(n))

lis = list(itertools.combinations(deta,2))

count  = 0

for i in lis:
    if c[i[0]] != c[i[1]]:
        for j in range(i[0]+1,i[1]):
            if j-i[0] != i[1]-j and c[i[0]] != c[j] and c[j] != c[i[1]]:
                count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    s =input()
    cnt = 0
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue
            for k in range(j+1, n):
                if s[i] == s[k] or s[j] == s[k]:
                    continue
                if j-i != k-j:
                    cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

count = 0
for i in r:
  for j in g:
    for k in b:
      if (i+j+k)/3 not in [i,j,k]:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n= int(input())
    s = str(input())
    ans = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range (j+1,n):
                t = {s[i], s[j], s[k]}
                if j-i != k-j and len(t) ==3:
                    ans +=1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n= int(input())
s = str(input())
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range (j+1,n):
            t = {s[i], s[j], s[k]}
            if j-i != k-j and len(t) ==3:
                ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

ans = 0
for x, y, z in combinations(range(n), 3):
    if y - x != z - y:
        if s[x] != s[y] and s[x] != s[z] and s[y] != s[z]:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

su = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            for lis in ['R','G','B']:
                if lis != s[i] and lis != s[j]:
                    try:
                        su -= s[2*j-i].count(lis)
                    except:
                        pass

print(su)

Submission status: Time Limit Exceeded

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

su = 0
for i in range(n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            for lis in ['R','G','B']:
                if lis != s[i] and lis != s[j]:
                   su += s[j+1:2*j-i].count(lis) + s[2*j-i+1:].count(lis)

print(su)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from itertools import combinations

N = int(input())
S = input()
count = 0

for i,j,k in combinations(range(N), 3):
    if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        a = sorted([i,j,k])
        if a[1]-a[0] != a[2]-a[1]:
            count+=1

print(count)

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                a = sorted([i,j,k])
                if a[1]-a[0] != a[2]-a[1]:
                    count+=1
print(int(count/6))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    S = LS()

    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)

    len_r = len(R)
    len_g = len(G)
    len_b = len(B)

    def g(lst, r,  j):
        l = -1
        while r - l > 1:
            m = (l + r) // 2
            if lst[m] <= j:
                l = m
            else:
                r = m
        return r


    def f(lst, r, out):
        l = -1
        while r - l > 1:
            m = (r + l) // 2
            if out < lst[m]:
                r = m
            elif out > lst[m]:
                l = m
            else:
                return True
        return False

    ans = 0
    for i in range(N):
        si = S[i]
        for j in range(i+1, N):
            sj = S[j]
            if si == sj: continue
            out = j + j - i
            # print(i, j, si, sj, out)
            if si == 'R':
                if sj == 'G':
                    # B
                    k = g(B, len_b, j)
                    # print(k)
                    ans += len_b - k
                    if f(B, len_b, out):
                        ans -= 1
                elif sj == 'B':
                    # G
                    k = g(G, len_g, j)
                    ans += len_g - k
                    if f(G, len_g, out):
                        ans -= 1
            elif si == 'G':
                if sj == 'R':
                    # B
                    k = g(B, len_b, j)
                    ans += len_b - k
                    if f(B, len_b, out):
                        ans -= 1
                elif sj == 'B':
                    # R
                    k = g(R, len_r, j)
                    ans += len_r - k
                    if f(R, len_r, out):
                        ans -= 1
            elif si == 'B':
                if sj == 'R':
                    # G
                    k = g(G, len_g, j)
                    ans += len_g - k
                    if f(G, len_g, out):
                        ans -= 1
                elif sj == 'G':
                    # R
                    k = g(R, len_r, j)
                    ans += len_r - k
                    if f(R, len_r, out):
                        ans -= 1
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

total = 0
for i in range(n-3):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if j-i == k-j:
        continue
      elif s[i] == s[j]:
        continue
      elif s[j] == s[k]:
        continue
      elif s[i] == s[k]:
        continue
      else:
        total += 1
        
print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
S=list(input())
ans=0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k] and j-i != k-j:
        ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())
ans=0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k] and j-i != k-j:
        ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

RGB = {"R":[0]*N, "G":[0]*N, "B":[0]*N}
for i in range(N):
    if S[i] == "R":
        RGB["R"][i] = 1
    elif S[i] == "G":
        RGB["G"][i] = 1
    else:
        RGB["B"][i] = 1

for k in RGB.keys():
    RGB[k] = list(itertools.accumulate(RGB[k]))

ans = 0
for i in range(N-2):
    l_i = S[i]
    for j in range(i+1, N-1):
        l_j = S[j]
        d = {"R", "G", "B"}
        if l_i != l_j:
            d.remove(l_i)
            d.remove(l_j)
            l_k = d.pop()
            ans += RGB[l_k][N-1] - RGB[l_k][j]
            if j*2 - i <= N-1:
                if S[j*2 - i] == l_k:
                    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(0,N-2) :
    for j in range(i+1,N-1) :
        for k in range(j+1,N) :
            if j - i != k -j :
                if (S[i] != S[j]) and (S[i] != S[k]) and (S[j] != S[k]) :
                    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

def check(i,j,N,x):
  A = S[j+1:].count(x)
  check_index=i+(j-i)*2
  if check_index<=N-1 and S[check_index]==x:
    A-=1
  return A

for i in range(len(S)-2):
  temp=['']*2
  temp[0]=S[i]
  for j in range(i+1,len(S)-1):
    if S[i]!=S[j]:
      temp[1]=S[j]
    else:
      continue
    if 'R' not in temp:
      ans += check(i,j,N,'R')
    elif 'G' not in temp:
      ans += check(i,j,N,'G')
    elif 'B' not in temp:
      ans += check(i,j,N,'B')
    continue

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
ans=0
minus=0
for i in range(len(S)-2):
  temp=['']*2
  temp[0]=S[i]
  for j in range(i+1,len(S)-1):
    if S[i]!=S[j]:
      temp[1]=S[j]
    else:
      continue
    if 'R' not in temp:
      ans +=S[j+1:].count('R')
      check_index=i+(j-i)*2
      if check_index<=N-1 and S[check_index]=='R':
        minus+=1
    if 'G' not in temp:
      ans +=S[j+1:].count('G')
      check_index=i+(j-i)*2
      if check_index<=N-1 and S[check_index]=='G':
        minus+=1
    if 'B' not in temp:
      ans +=S[j+1:].count('B')
      check_index=i+(j-i)*2
      if check_index<=N-1 and S[check_index]=='B':
        minus+=1
    continue

print(ans-minus)

Submission status: Time Limit Exceeded

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

alphabet_dict = {}
for i in range(N):
    alphabet = S[i]
    if alphabet in  alphabet_dict.keys():
        alphabet_dict[alphabet].append(i)
    else:
        alphabet_dict[alphabet] = [i]

# 全集合
result = 1
for key in alphabet_dict.keys():
    result*=len(alphabet_dict[key])

# rgb三色揃っている
if len(alphabet_dict.keys())==3:
    for i in range(N):
        for j in range(i, N):
            k = 2*j-i
            if k > N:
                break
            keys = []
            for key in alphabet_dict.keys():
                if i in alphabet_dict[key]:
                    keys.append(key)
                if j in alphabet_dict[key]:
                    keys.append(key)
                if k in alphabet_dict[key]:
                    keys.append(key)
            if len(set(keys))==3:
                result-=1
else:
    result = 0
print(result)

Submission status: Time Limit Exceeded

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

for i in range(len(S)-2):
  temp=['']*2
  temp[0]=S[i]
  for j in range(i+1,len(S)-1):
    if S[i]!=S[j]:
      temp[1]=S[j]
    else:
      continue
    for k in range(j+1, len(S)):
      if (S[k] not in temp) and (j-i != k-j):
        ans+=1
      else:
        continue
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] == 'R':
            if S[j] == 'R':
                continue
            elif S[j] == 'G':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('B')
                    total += S[2*j-i+1:N].count('B')
                else:
                    total += S[j+1:N].count('B')
            elif S[j] == 'B':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('G')
                    total += S[2*j-i+1:N].count('G')
                else:
                    total += S[j+1:N].count('G')
        elif S[i] == 'G':
            if S[j] == 'G':
                continue
            elif S[j] == 'B':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('R')
                    total += S[2*j-i+1:N].count('R')
                else:
                    total += S[j+1:N].count('R')
            elif S[j] == 'R':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('B')
                    total += S[2*j-i+1:N].count('B')
                else:
                    total += S[j+1:N].count('B')
        elif S[i] == 'B':
            if S[j] == 'B':
                continue
            elif S[j] == 'G':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('R')
                    total += S[2*j-i+1:N].count('R')
                else:
                    total += S[j+1:N].count('R')
            elif S[j] == 'R':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('G')
                    total += S[2*j-i+1:N].count('G')
                else:
                    total += S[j+1:N].count('G')

print(total)