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:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
#################################### ########
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
#################################### ########
n=int(input())
s=input()
R=s.count("R")
G=s.count("G")
B=s.count("B")

ans=R*G*B
for a in range(1,n):
    for b in range(0,n):
        if(b>=n or b+a>=n or b+a+a>=n):continue
        if s[b]!=s[b+a] and s[b+a]!=s[b+a+a] and s[b+a+a]!=s[b]:
            ans-=1
print(ans)

Submission status: Accepted

Solution code:



ans = r = g = b = rg = gb = br = 0

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

for ch in s:
    if ch == 'R':
        r += 1
        br += b
        rg += g
        ans += gb

    if ch == 'B':
        b += 1
        br += r
        gb += g
        ans += rg

    if ch == 'G':
        g += 1
        rg += r
        gb += b
        ans += br

c = 0

for i in range(1, n // 2 + 1):
    for j in range(0, n - 1):

        if j + 2 * i >= n:
            break

        ch1 = s[j]
        ch2 = s[j + i]
        ch3 = s[j + 2 * i]

        if len({ch1, ch2, ch3}) == 3:
            c += 1

print (ans - c)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
import collections
temp1 = 0
for j in range(1,n-1):
    i,k = j-1,j+1
    while i >= 0 and k < n:
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            temp1 += 1
        i,k = i-1,k+1
c = collections.Counter(s)
temp2 = 1
for key in "RGB":
    temp2 *= c[key]
print(temp2-temp1)

Submission status: Accepted

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

r = 0
g = 0
b = 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(1, n//2+1):
    for j in range(n):
        if j+2*i < n:
            if s[j] != s[j+i] and s[j+i] != s[j+2*i] and s[j] != s[j+2*i]:
                #print(j, j+i, j+2*i)
                ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = str(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
for r in R:
    for g in G:
        ans += len(B)
        mi,ma = min(r,g),max(r,g)
        p = bisect_left(B,2*ma-mi)
        if 0<= p <= len(B)-1 and B[p] == 2*ma-mi and 2*ma-mi > ma:
            ans -= 1
        p = bisect_left(B,(ma+mi)/2)
        if 0<= p <= len(B)-1 and B[p] == (ma+mi)/2 and mi<B[p]<ma:
            ans -= 1
        p = bisect_left(B,2*mi-ma)
        if 0 <= p <= len(B)-1 and B[p] == 2*mi-ma and B[p]<mi:
            ans -= 1
print(ans)

Submission status: Accepted

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys


def _s(): return sys.stdin.readline().strip()


def _i(): return int(sys.stdin.readline().strip())


def main():
    n = _i()
    s = _s()
    c = {
        "R": [0] * (n + 1),
        "G": [0] * (n + 1),
        "B": [0] * (n + 1)
    }
    j = n
    for rgb in reversed(s):
        j -= 1
        for _rgb in "RGB":
            c[_rgb][j] = c[_rgb][j+1]
        c[rgb][j] += 1

    ans = 0
    rgb = {"R", "G", "B"}
    for i in range(n-2):
        c1 = s[i]
        for j in range(i+1, n-1):
            c2 = s[j]
            if c1 == c2:
                continue
            #
            c3 = (rgb - {c1, c2}).pop()
            ans += c[c3][j+1]
            k = 2 * j - i
            if k < n and s[k] == c3:
                ans -= 1
    return ans


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

Submission status: Accepted

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

S = S.replace('R', '0')
S = S.replace('G', '1')
S = S.replace('B', '2')
lis = [[0, 0, 0] for _ in range(N)]
index_lis = [0, 2, 1, 0]
for i in range(N):
  j = N-1-i
  for k in range(j):
    lis[k][int(S[j])] += 1


count = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    if S[i] != S[j]:
      if 2*j-i < N:
        if S[2*j-i] == S[i] or S[2*j-i] == S[j]:
          count += lis[j][index_lis[int(S[i])+int(S[j])]]
        else:
          count += lis[j][int(S[2*j-i])] - 1
      else:
        count += lis[j][index_lis[int(S[i])+int(S[j])]]
print(count)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
r=0
g=0
b=0
for i in range(n):
    if s[i]=='R':
        r+=1
    elif s[i]=='G':
        g+=1
    else:
        b+=1
answer=r*g*b
for j in range(1,int(n/2)+1):
    for k in range(0,n-2*j):
        if s[k]!=s[k+j] and s[k]!=s[k+2*j] and s[k+j]!=s[k+2*j]:
            answer-=1
print(answer)

Submission status: Accepted

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

d = {
    'R': list(),
    'G': list(),
    'B': list()
}


for i, c in enumerate(S):
    d[c].append(i+1)

all = len(d['R']) * len(d['G']) * len(d['B'])

for c in 'RGB':
    d[c] = sorted(d[c])


# decide twice
for c in 'RGB':
    s = set([2 * x for x in d[c]])
    cs = [x for x in 'RGB' if x != c]

    for i in d[cs[0]]:
        for j in d[cs[1]]:
            if (i+j) in s:
                all -= 1

print(all)

Submission status: Accepted

Solution code:
from sys import stdin
import bisect
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    S=readline().strip()

    res=0

    R=[]
    G=[]
    B=[]
    flags=[""]*N
    for i in range(N):
        if S[i]=="R":
            R.append(i)
            flags[i]="R"
        elif S[i]=="G":
            G.append(i)
            flags[i]="G"
        else:
            B.append(i)
            flags[i]="B"
    
    #Bが最後
    for i in range(len(R)):
        for j in range(len(G)):
            n=max(R[i],G[j])
            k=bisect.bisect_left(B,n)
            res+=len(B)-k
            if n+n-min(R[i],G[j])<N:
                if flags[n+n-min(R[i],G[j])]=="B":
                    res-=1
    
    for i in range(len(R)):
        for j in range(len(B)):
            n=max(R[i],B[j])
            k=bisect.bisect_left(G,n)
            res+=len(G)-k
            if n+n-min(R[i],B[j])<N:
                if flags[n+n-min(R[i],B[j])]=="G":
                    res-=1

    for i in range(len(B)):
        for j in range(len(G)):
            n=max(B[i],G[j])
            k=bisect.bisect_left(R,n)
            res+=len(R)-k
            if n+n-min(B[i],G[j])<N:
                if flags[n+n-min(B[i],G[j])]=="R":
                    res-=1

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

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    S=tuple(input().strip())
    r,g,b=0,0,0
    for s in S:
        if s=='R':
            r+=1
        elif s=='G':
            g+=1
        else:
            b+=1
    ans=r*g*b
    #print(ans)
    for i in range(n-2):
        for j in range(i+1,n-1):
            k=i+(j-i)*2
            if k>=n:
                break
            #print(i,j,k)
            #print(S[i],S[j],S[k])
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                #print(i,j,k)
                ans-=1
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

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

dic = {}
dic['R'] = []
dic['G'] = []
dic['B'] = []

for i in range(n):
    dic[s[i]].append(i)

rem = {}

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

res=0

for i in range(n):
    neigh1 = rem[s[i]][0]
    neigh2 = rem[s[i]][1]
    ind = bisect.bisect_right(dic[neigh1],i)
    for j in range(ind, len(dic[neigh1])):
        node = dic[neigh1][j]
        nind = bisect.bisect_right(dic[neigh2],node)

        l = max(0,len(dic[neigh2])-nind)

        diff = node-i
        if node+diff>=nind and node+diff<n and s[node+diff]==neigh2:
            l-=1

        res+=l

    ind = bisect.bisect_right(dic[neigh2],i)
    for j in range(ind, len(dic[neigh2])):
        node = dic[neigh2][j]
        nind = bisect.bisect_right(dic[neigh1],node)

        l = max(0,len(dic[neigh1])-nind)

        diff = node-i
        if node+diff>=nind and node+diff<n and s[node+diff]==neigh1:
            l-=1

        res+=l

print(res)

Submission status: Accepted

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

Submission status: Accepted

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

accum=[]
num_r=num_g=num_b=0
for i in range(N):
  if S[i]=="R":
    num_r+=1
  elif S[i]=="G":
    num_g+=1
  else:
    num_b+=1
  accum.append((num_r,num_g,num_b))

dp=[0]*N
for i in range(3,N):
  dp[i]=dp[i-1]
  nr,ng,nb=accum[i-1]
  if S[i]=="R":
    dp[i]+=ng*nb
  elif S[i]=="G":
    dp[i]+=nr*nb
  else:
    dp[i]+=ng*nr
    
  for j in range(1,i//2+1):
    #print(i,i-j,i-2*j)
    set_rgb=set()
    set_rgb.add(S[i])
    set_rgb.add(S[i-j])
    set_rgb.add(S[i-2*j])
    if len(set_rgb)==3:
      dp[i]-=1
      
print(dp[-1])

Submission status: Accepted

Solution code:
import bisect

def brute():
    N=int(input())
    S=input()

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

    ans=0
    for i,c in enumerate(S):
        if c=="R":
            R.append(i)
        elif c=="B":
            B.append(i)
        else:
            G.append(i)

    for mid in range(1,N-1):
        if S[mid]=="R":
            low_1=bisect.bisect_left(G,mid)
            low_2 =bisect.bisect_left(B,mid)
            high_1=len(G)-low_1
            high_2=len(B)-low_2
        elif S[mid]=="B":
            low_1=bisect.bisect_left(G,mid)
            low_2 =bisect.bisect_left(R,mid)
            high_1=len(G)-low_1
            high_2=len(R)-low_2
        else:#G
            low_1=bisect.bisect_left(B,mid)
            low_2 =bisect.bisect_left(R,mid)
            high_1=len(B)-low_1
            high_2=len(R)-low_2

        dup = sum([1 if a!=b and a!=S[mid] and b!=S[mid]else 0 for a,b in zip(reversed(S[:mid]),S[mid+1:])])
        t = low_1*high_2 + low_2*high_1
        ans+=t
        ans -= dup
    print(ans)

brute()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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

rs, gs, bs = [], [], []
for l, c in enumerate(s):
  if c == 'R':
    rs.append(l)
  if c == 'G':
    gs.append(l)
  if c == 'B':
    bs.append(l)
sbs = set(bs)

ans = 0
for r in rs:
  for g in gs:
    m = min(r, g)
    M = max(r, g)
    notbs = [m - (M - m), M + (M - m)]
    if (M + m) % 2 == 0:
      notbs.append((M + m) // 2)
    
    dprint(m, M, notbs, sbs)
    
    # a = len(sbs - set(notbs))

    a = len(sbs)
    for notb in notbs:
      if notb in sbs:
        a -= 1
    if a > 0:
      ans += a


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
#import fractions

n = int(input())
#tmp = input().split()
#n,m,k = list(map(lambda a: int(a), tmp))
s=input()

num_R=0
num_G=0
num_B=0

for i in range(n):
	if(s[i]=="R"):
		num_R+=1
	if(s[i]=="G"):
		num_G+=1
	if(s[i]=="B"):
		num_B+=1
total=num_R*num_G*num_B
#print(total)


tmp=n//2
#print(tmp)
for i in range(1,tmp+1):
	for j in range(n-i*2):
		if(s[j]!=s[j+i] and s[j]!=s[j+i*2] and s[j+i]!=s[j+i*2]):
			total-=1

#print(s)
print(total)

Submission status: Accepted

Solution code:
# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from math import gcd

def main():
		n = int(input())
		s = input()
		ans = 0
		b = [0]*n
		g = [0]*n
		r = [0]*n
		for i in range(n):
			if s[i]=="B":
				b[i]=1
			if s[i]=="G":
				g[i]=1
			if s[i]=="R":
				r[i]=1
		pre_r = [r[0]]
		pre_b = [b[0]]
		pre_g = [g[0]]
		for i in range(1,n):
			pre_r.append(pre_r[i-1]+r[i])
			pre_g.append(pre_g[i-1]+g[i])
			pre_b.append(pre_b[i-1]+b[i])	
		ms = {"R", "G", "B"}
		ans = 0
		for i in range(n):
			for j in range(i+1, n):
				if (s[i]!=s[j]):
					z = set([s[i], s[j]])
					x = list(ms.difference(z))[0]
					# print(i, j, ans)
					if x=="B":
						tmp = pre_b[j]-pre_b[i]
						if (i+j)/2 == int((i+j)/2):
							if b[(i+j)//2] == 1:
								tmp-=1
						ans += max(0, tmp)
					if x=="G":
						tmp = pre_g[j]-pre_g[i]
						# print((i+j)/2, "bahar")
						if (i+j)/2 == int((i+j)/2):
							# print("andar")
							# print()
							if g[(i+j)//2] == 1:
								tmp-=1
								# print("tmp", tmp)
						ans += max(0, tmp)					
					if x=="R":
						tmp = pre_r[j]-pre_r[i]
						if (i+j)/2 == int((i+j)/2):
							if r[(i+j)//2] == 1:
								tmp-=1
						ans += max(0, tmp)
		print(ans)
		
		


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b"\n") + (not b)
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode("ascii"))
		self.read = lambda: self.buffer.read().decode("ascii")
		self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#!python3

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


def main():
    r, g, b = 0, 0, 0
    rg, gr = 0, 0
    rb, br = 0, 0
    gb, bg = 0, 0
    ans = 0
    for s in S[::-1]:
        if s == "R":
            ans += gb + bg
            rg += g
            rb += b
            r += 1
        if s == "G":
            ans += rb + br
            gr += r
            gb += b
            g += 1
        if s == "B":
            ans += rg + gr
            br += r
            bg += g
            b += 1
    
    lim = (N - 1) // 2 + 1
    for i in range(1, lim):
        lim2 = N - 2 * i
        for j in range(lim2):
            if S[j] != S[j+i] and S[j+i] != S[j+2*i] and S[j] != S[j+2*i]:
                ans -= 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
R = [0]*N
G = [0]*N
B = [0]*N
out = 0
for i in range(N):
    if S[i]=="R":
        R[i]+=1
    if S[i]=="G":
        G[i]+=1
    if S[i]=="B":
        B[i]+=1

SB = sum(B)
for i in range(N):
    for j in range(N):
        X = R[i]
        Y = G[j]
        if (X==1)and(Y==1):
            out += SB
            D = abs(i-j)

            L1 = max(i,j)+D
            if L1<N:
                out += -1*B[L1]
            L2 = min(i,j)-D
            if 0<=L2:
                out += -1*B[L2]
            if D%2==0:
                L3 = min(i,j)+D//2
                out += -1*B[L3]
print(out)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys


N = int(input())
S = list(input())
#%%
r_ruiseki = [0]*(N+1)
b_ruiseki = [0]*(N+1)
g_ruiseki = [0]*(N+1)
for i in range(N):
    r_ruiseki[i+1] = r_ruiseki[i] + (S[i]=='R')
    g_ruiseki[i+1] = g_ruiseki[i] + (S[i]=='G')
    b_ruiseki[i+1] = b_ruiseki[i] + (S[i]=='B')
pos_r = []
pos_b = []
pos_g = []
for i,s in enumerate(S):
    if s=='R':
        pos_r.append(i)
    elif s=='B':
        pos_b.append(i)
    else:
        pos_g.append(i)

ans = 0
for i in pos_r:
    for j in pos_b:
        if j-i<=1:
            continue
        ans += g_ruiseki[j+1] - g_ruiseki[i]
        if (i&1 == j&1):
            if S[(i+j)//2]=='G':
                ans -= 1
    

for i in pos_b:
    for j in pos_r:
        if j-i<=1:
            continue
        ans += g_ruiseki[j+1] - g_ruiseki[i]
        if (i&1 == j&1):
            if S[(i+j)//2]=='G':
                ans -= 1
    

for i in pos_r:
    for j in pos_g:
        if j-i<=1:
            continue
        ans += b_ruiseki[j+1] - b_ruiseki[i]
        if (i&1 == j&1):
            if S[(i+j)//2]=='B':
                ans -= 1
    
for i in pos_g:
    for j in pos_r:
        if j-i<=1:
            continue
        ans += b_ruiseki[j+1] - b_ruiseki[i]
        if (i&1 == j&1):
            if S[(i+j)//2]=='B':
                ans -= 1
    

for i in pos_g:
    for j in pos_b:
        if j-i<=1:
            continue
        ans += r_ruiseki[j+1] - r_ruiseki[i]
        if (i&1 == j&1):
            if S[(i+j)//2]=='R':
                ans -= 1
    
for i in pos_b:
    for j in pos_g:
        if j-i<=1:
            continue
        ans += r_ruiseki[j+1] - r_ruiseki[i]
        if (i&1 == j&1):
            if S[(i+j)//2]=='R':
                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")
cou = 0
for i in range((N - 3) // 2 + 1):
    for j in range(N - 2 - 2 * i):
        if S[j] != S[i + j + 1] and S[i + j + 1] != S[2 * i + j + 2] and S[j] != S[2 * i + j + 2]:
            cou += 1
print(r * g * b - cou)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = s.count('R')*s.count('G')*s.count('B')
for begin in range(n):
    step = 1
    while begin+2*step<n:
        if s[begin]!=s[begin+step] and s[begin+step]!=s[begin+2*step] and s[begin+2*step]!=s[begin]:
            ans -= 1
        step += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    S = input().strip()
    
    v = 0
    R = 0
    G = 0
    B = 0
    for i in range(N):
        if S[i] == "R":
            R += 1
        elif S[i] == "G":
            G += 1
        else:
            B += 1

        if i == 0 or i == N - 1:
            continue

        for d in range(1, min(i, N - i - 1) + 1):
            if S[i] == S[i - d]:
                continue
            if S[i] == S[i + d]:
                continue
            if S[i - d] == S[i + d]:
                continue
            v += 1

    print(R * G * B - v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(n, s):

    r_list = [i for i in range(n) if s[i] == "R"]
    g_list = [i for i in range(n) if s[i] == "G"]
    # b_list = [i for i in range(n) if s[i] == "B"]
    b_dict = {i: 1 for i in range(n) if s[i] == "B"}

    res = len(r_list) * len(g_list) * len(b_dict.keys())
    for i in r_list:
        for j in g_list:
            # candidate
            m, n = min(i, j), max(i, j)
            if n + (n - m) in b_dict.keys():
                res -= 1
            if m - (n - m) in b_dict.keys():
                res -= 1
            if (n - m) % 2 == 0 and (n + m) // 2 in b_dict.keys():
                res -= 1

    return res


def main():
    n = int(input())
    s = input()
    res = solve(n, s)
    print(res)


def test():
    assert solve(4, "RRGB") == 1
    assert solve(39, "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB") == 1800


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

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

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

ans=r*g*b
for i in range(1,n):
    for j in range(n):
        if(j+i*2>=n):break
        d1,d2,d3=s[j],s[j+i],s[j+i*2]
        if(not(d1==d2 or d2==d3 or d1==d3)):ans-=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
r = [0]*n
g = [0]*n
b = [0]*n
if s[0] == "R": r[0] = 1
elif s[0] == "G": g[0] = 1
else: b[0] = 1
for i in range(1,n):
    if s[i] == "R": r[i] = 1
    elif s[i] == "G": g[i] = 1
    else: b[i] = 1
    r[i] += r[i-1]
    g[i] += g[i-1]
    b[i] += b[i-1]
ans = 0
for i in range(n):
    for j in range(i+1,n):
        if s[i] == s[j]: continue
        d = j - i
        t = (s[i],s[j])
        if "R" not in t:
            ans += r[n-1]-r[j]
            if j+d >= n: continue
            if s[j+d] == "R": ans -= 1
        elif "G" not in t:
            ans += g[n-1]-g[j]
            if j+d >= n: continue
            if s[j+d] == "G": ans -= 1
        else:
            ans += b[n-1]-b[j]
            if j+d >= n: continue
            if s[j+d] == "B": ans -= 1
        
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################

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

num = [[0,0,0,0,0] for i in range(n)]
ans = 0

info = []
for i in range(n):
    if(s[i]=='R'):
        info.append(0)
    elif(s[i]=='G'):
        info.append(1)
    else:
        info.append(2)
        
#print(info)

for i in range(n):
    for j in range(i):
        if((3+info[i]-info[j])%3 == 1):
            num[i][0]+=1
        elif((3+info[i]-info[j])%3 == 2):
            num[i][1]+=1
    for j in range(n-1-i):
        if((3+info[i] - info[i+1+j])%3 == 1):
            num[i][2]+=1
        elif((3+info[i] - info[i+1+j])%3 == 2):
            num[i][3]+=1
    for j in range(min(i,n-1-i)):
        if(s[i-j-1]!=s[i+1+j] and s[i]!=s[i-j-1] and s[i]!=s[i+1+j]):
            num[i][4]+=1
            #print(j,i,i+1+j)
    #print(num[i])
    ans += num[i][0]*num[i][3] + num[i][1]*num[i][2] - num[i][4]

    
print(ans)