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:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    S=input()
    R,G,B=S.count('R'),S.count('G'),S.count('B')
    ALL = R*G*B
    for a in range(N):
        for b in range(a+1, N):
            c = b + (b-a)
            if c >= N:
                continue
            if S[a] != S[b] and S[b] != S[c] and S[c] != S[a]:
                ALL -= 1
    print(ALL)



main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from itertools import permutations
import bisect
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    ci = defaultdict(list)
    for i, c in enumerate(S):
        ci[c].append(i)

    ans = 0
    for c1, c2 , c3 in permutations('RGB', r=3):
        for i in ci[c1]:
            for j in range(bisect.bisect_left(ci[c2], i), len(ci[c2])):
                j = ci[c2][j]
                ans += len(ci[c3]) - bisect.bisect_left(ci[c3], j)
                d = (j-i)+j
                k = bisect.bisect_left(ci[c3], d)
                if k < len(ci[c3]) and ci[c3][k] == d:
                    ans -= 1
    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
r_array = []
g_array = []
r, g, b = 0, 0, 0
for i, s in enumerate(S):
    if s == "R":
        r += 1
        r_array.append(i)
    elif s == "G":
        g += 1
        g_array.append(i)
    else:
        b += 1

ans = r * g * b

for r in r_array:
    for g in g_array:
        c1 = 2 * r - g
        if c1 >= 0 and c1 < N and S[c1] == "B":
            ans -= 1
        c2 = r + g
        if (r + g) % 2 == 0 and S[(r + g) // 2] == "B":
            ans -= 1
        c3 = 2 * g - r
        if c3 < N and c3 >= 0 and S[c3] == "B":
            ans -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
s = S()
r = 0
g = 0
b = 0
for i in s:
    if i == 'R':
        r += 1
    elif i == 'G':
        g += 1
    else:
        b += 1

ans = r * g * b
for gap in range(2000):
    for start in range(4000):
        if start + gap * 2 >= len(s):
            break
        else:
            if s[start] != s[start + gap] != s[start + gap * 2] != s[start]:
                ans -= 1


print(ans)

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N = Int()
S = input()

ans = [0]*8
ans[0] = 1
D = {'R':1, 'G':2, 'B':4}

for i in range(N):
    #print(ans)
    for j in range(8):
        k = 7-j
        if k|D[S[i]] != k:
            ans[k|D[S[i]]] += ans[k]
#print(ans)
tmp = 0
for i in range(N):
    for j in range(1,N):
        if i+2*j < N:
            if S[i]!=S[i+j] and S[i] != S[i+2*j] and S[i+j] != S[i+2*j]:
                tmp += 1
print(ans[7]-tmp)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
ss = [0] * n
for i,t in enumerate(s):
    if t == 'R':
        ss[i] = 0
    elif t == 'G':
        ss[i] = 1
    else:
        ss[i] = 2
color = [[0] * 3 for _ in range(n)] 
color[0][ss[0]] = 1
for i,t in enumerate(ss):
    if i == 0:
        continue
    for j in range(3):
        if t == j:
            color[i][j] = color[i-1][j] + 1
        else:
            color[i][j] = color[i-1][j]
res = 0
for i in range(n-1):
    for j in range(i+1,n):
        if ss[i] == ss[j]:
            continue
        c = j-i
        yet = -1
        for _ in range(3):
            if ss[i] == _ or ss[j] == _ :
                continue
            yet = _
        res += color[-1][yet] - color[j][yet]
        if j+c < n and ss[j+c] == yet:
            res -= 1
print(res)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
cnt = [[0]*3 for i in range(n+1)]
for i,c in enumerate(s):
    if c == 'R':
        cnt[i+1][0] += 1
    if c == 'G':
        cnt[i+1][1] += 1
    if c == 'B':
        cnt[i+1][2] += 1
    for j in range(3):
        cnt[i+1][j] += cnt[i][j]
ans = 0
for i in range(1,n-1):
    if s[i] == 'R':
        ans += cnt[i][1]*(cnt[n][2]-cnt[i][2])
        ans += cnt[i][2]*(cnt[n][1]-cnt[i][1])
    elif s[i] == 'G':
        ans += cnt[i][0]*(cnt[n][2]-cnt[i][2])
        ans += cnt[i][2]*(cnt[n][0]-cnt[i][0])
    else:
        ans += cnt[i][1]*(cnt[n][0]-cnt[i][0])
        ans += cnt[i][0]*(cnt[n][1]-cnt[i][1])
    for j in range(1,min(i+1,n-i)):
        if s[i-j] != s[i] and s[i] != s[i+j] and s[i-j] != s[i+j]:
            ans -= 1
print(ans)

Submission status: Accepted

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

N=int(input())
s=list(input())

d=1
p1=0
p2=1
p3=2

cR=s.count("R")
cG=s.count("G")
cB=s.count("B")
# print(cR,cG,cB)
count=0
while d<N:
	# print(p1,p2,p3,count)
	if p1<N and p2<N and p3<N:
		if s[p1]!=s[p2] and s[p2]!=s[p3] and s[p3]!=s[p1]:
			count+=1
		p1+=1
		p2+=1
		p3+=1
	else:
		d+=1
		p1=0
		p2=p1+d
		p3=p2+d

ans=cR*cG*cB-count
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
count = {"R":[],"G":[],"B":[]}

for i in range(N):
    count[S[i]].append(i)
ans = len(count["R"])*len(count["G"])*len(count["B"])
for r in range(N):
    for g in range(r+1,N):
        if  0 <= g*2-r < N and ord(S[g*2-r]) + ord(S[r]) + ord(S[g]) == 219:
            ans -= 1

print(ans)

Submission status: Accepted

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

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

R_append = R.append
G_append = G.append
B_append = B.append

for i in range(N):
    if S[i] == 'R':
        R_append(i)
    elif S[i] == 'G':
        G_append(i)
    else:
        B_append(i)

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

for r in R:
    for g in G:
        tmp = abs(r - g)
        small = min(r, g)
        large = max(r, g)
        if small >= tmp:
            if S[small - tmp] == 'B':
                ans -= 1
        if large + tmp < N:
            if S[large + tmp] == 'B':
                ans -= 1
        if tmp % 2 == 0:
            if S[small + tmp // 2] == 'B':
                ans -= 1

print (ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
from bisect import bisect_left
MOD = 10**9 + 7
INF = 1 << 20


def main():
    n = getN()
    s = input().strip()

    rs = []
    gs = []
    bs = []
    for i, c in enumerate(s):
        if c == "R":
            rs.append(i)
        elif c == "G":
            gs.append(i)
        else:
            bs.append(i)


    lr, lg, lb = len(rs), len(gs), len(bs)
    ans = 0
    # print(s, s[1])
    tgt = {"R": rs, "G":gs, "B": bs }
    idxs = {"R": lr, "G": lg, "B": lb}
    for i in range(n-1):
        first = s[i]
        for j in range(i+1, n):
            # first = s[i]
            second = s[j]
            # print(i, j)
            if first == second:
                continue
            else:
                # print(first, second)
                rem = ["R", "G", "B"]
                rem.remove(first)
                rem.remove(second)
                remm = rem[0]
                # print(i, j, remm)
                ans += idxs[remm] - bisect_left(tgt[remm], j)
                if (2*j - i) < n and s[2*j - i] == remm:
                    ans -= 1
                    # print("substracted")
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

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

rcnt = s.count("R")
gcnt = s.count("G")
bcnt = s.count("B")
total = rcnt * gcnt * bcnt

for i, ch in enumerate(s):
    left = s[:i]
    right = s[i+1:]
    left.reverse()
    for ll, rr in zip(left, right):
        if ll != rr and ll != ch and rr != ch:
            total -= 1

print(total)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

ANS=0

CL=[[0,0,0] for i in range(N+1)]
for i in range(N-1,-1,-1):
    for j in range(3):
        CL[i][j]=CL[i+1][j]

    CL[i][S[i]]+=1


for i in range(N):
    for j in range(i+1,N):
        if S[i]!=S[j]:
            ANS+=CL[j][3-S[i]-S[j]]

            if j+(j-i)<N:
                x=j+(j-i)
                if S[x]!=S[i] and S[x]!=S[j]:
                    ANS-=1

print(ANS)

Submission status: Accepted

Solution code:
from sys import stdin

input = stdin.readline

n = int(input())
a = input().rstrip()
cnt = 0

for x in range(n - 2):
    for z in range(x + 2, n, 2):
        y = (x + z) // 2
        if a[x] == a[y] or a[y] == a[z] or a[z] == a[x]:
            continue

        cnt += 1

print(a.count('R') * a.count('G') * a.count('B') - cnt)

Submission status: Accepted

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

import sys, bisect
sys.setrecursionlimit(300000)

def solve(N: int, S: str):
    tmp = {'R': [], 'G': [], 'B': []}
    for i, c in enumerate(S):
        tmp[c].append(i)

    ret = 0
    x = len(tmp['R'])
    y = len(tmp['G'])
    z = len(tmp['B'])
    ret = x * y * z
    for r in tmp['R']:
        for g in tmp['G']:
            d = abs(g - r)
            if g > r:
                t = g + d
            else:
                t = r + d
            idx = bisect.bisect_left(tmp['B'], t)
            if idx < z and tmp['B'][idx] == t:
                ret -= 1
    for r in tmp['R']:
        for b in tmp['B']:
            d = abs(b - r)
            if b > r:
                t = b + d
            else:
                t = r + d
            idx = bisect.bisect_left(tmp['G'], t)
            if idx < y and tmp['G'][idx] == t:
                ret -= 1
    for g in tmp['G']:
        for b in tmp['B']:
            d = abs(b - g)
            if b > g:
                t = b + d
            else:
                t = g + d
            idx = bisect.bisect_left(tmp['R'], t)
            if idx < x and tmp['R'][idx] == t:
                ret -= 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import *
import sys
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
S = inp()

NO = {}
for c in 'RBG':
    NO[c] = S.count(c)

left = {}
nbr = {k:0 for k in 'RGB'}
for i, c in enumerate(S):
    nbr[c] += 1
    for c in 'RBG':
        left[i,c] = NO[c] - nbr[c]

sm = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]: continue
        c = 'RGB'.replace(S[i], '').replace(S[j], '')
        cnt = left[j,c]
        k = 2*j - i
        if k < N and S[k] == c:
            cnt -= 1
        sm += cnt
print(sm)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def solve(N, S):
    C = {"R": 0, "G": 0, "B": 0}
    ans = 0
    for c in S:
        if c == "B":
            ans += C["R"] * C["G"]
            C["B"] += 1
        elif c == "G":
            ans += C["R"] * C["B"]
            C["G"] += 1
        elif c == "R":
            ans += C["B"] * C["G"]
            C["R"] += 1

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


if __name__ == "__main__":
    N = int(input())
    S = input()
    print(solve(N, S))

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    S = input()
    count = {'R':0, 'G': 0, 'B': 0}
    for c in S: count[c] += 1

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

    ans = count['R'] * count['G'] * count['B']

    return ans - remove

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

Submission status: Accepted

Solution code:
n = int(input())
d = input()
r = 0
g = 0
b = 0
for i in range(n):
  if d[i] == 'R':
    r += 1
  elif d[i] == 'G':
    g += 1
  else:
    b += 1
ans = r * g * b
for i in range(n):
  for j in range(i+1,n):
    if (i+j) % 2 == 1:
      continue
    k = (i+j) // 2
    if d[i] != d[j] and d[i] != d[k] and d[j] != d[k]:
      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] == 'B':
        b += 1
    else:
        g += 1

ans = r*g*b

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
nr = 0
ng = 0
nb = 0
for i in range(n):
    if s[i] == "R":
        nr += 1
    elif s[i] == "G":
        ng += 1
    else:
        nb += 1
        
ans = nr * ng * nb
#print(ans)
for i in range(1,(n-1)//2+1):
    for j in range(n-i*2):
        if s[j] != s[j+i] and s[j] != s[j+i*2] and s[j+i] != s[j+i*2]:
            ans -= 1
            
print(ans)

Submission status: Accepted

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

r=[0]*(n+1)
g=[0]*(n+1)
b=[0]*(n+1)

for i in reversed(range(n)):
    if s[i]=='R':
        r[i]=r[i+1]+1
        b[i]=b[i+1]
        g[i]=g[i+1]
    if s[i]=='B':
        r[i]=r[i+1]
        b[i]=b[i+1]+1
        g[i]=g[i+1]
    if s[i]=='G':
        r[i]=r[i+1]
        b[i]=b[i+1]
        g[i]=g[i+1]+1

ans=0

for i in range(n):
    for j in range(i+1,n):
        if s[i]!=s[j]:
            if s[i] != 'R' and s[j] != 'R':
                ans+=r[j]
                if (2*j-i)<n and s[2*j-i] == 'R':
                    ans-=1
            if s[i] != 'G' and s[j] != 'G':
                ans+=g[j]
                if (2*j-i)<n and s[2*j-i] == 'G':
                    ans-=1
            if s[i] != 'B' and s[j] != 'B':
                ans+=b[j]
                if (2*j-i)<n and s[2*j-i] == 'B':
                    ans-=1

print(ans)

Submission status: Accepted

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

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

ans = r*g*b

for i in range(1,n//2 + 10):
    for j in range(n):
        if(j + i*2 >= n):
            break
        a,b,c = s[j],s[j+i],s[j+i*2]
        if(a!=b)&(b!=c)&(a!=c):
            ans -= 1

print(ans)

Submission status: Accepted

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

count = [0]*3

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

ans = count[0]*count[1]*count[2]

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

print(ans)

Submission status: Accepted

Solution code:

N = int(input())

S = input()

R = 0
G = 0
B = 0

for i in S:
    if i == "R":
        R += 1
    elif i == "G":
        G += 1
    else:
        B += 1

ans = R*G*B

now = [0,0,0]
for i in range(1,N):

    for j in range(N):

        if j+2*i >= N:
            break

        now = [0,0,0]

        for l in range(3):
            if S[j+l*i] == "R":
                now[0] += 1
            elif S[j+l*i] == "G":
                now[1] += 1
            else:
                now[2] += 1

        if now[0] == 1 and now[1] == 1 and now[2] == 1:
            ans -= 1

print (ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = input()
R = [0]*n
G = [0]*n
B = [0]*n
for i in range(n):
    if s[i] == 'G':
        G[i] = 1
    elif s[i] == 'B':
        B[i] = 1
    else:
        R[i] = 1

R = list(accumulate(R))
G = list(accumulate(G))
B = list(accumulate(B))

ans = 0
for i in range(n):
    if s[i] == 'R':
        for j in range(i+1,n):
            if s[j] == 'B':
                ans += G[-1] - G[j]
                if j + (j-i) < n:
                    if s[j+(j-i)] == 'G':
                        ans -= 1
            elif s[j] == 'G':
                ans += B[-1] - B[j]
                if j + j-i < n:
                    if s[j+(j-i)] == 'B':
                        ans -= 1
    elif s[i] == 'B':
        for j in range(i+1,n):
            if s[j] == 'G':
                ans += R[-1] - R[j]
                if j + (j-i) < n:
                    if s[j+(j-i)] == 'R':
                        ans -= 1
            elif s[j] == 'R':
                ans += G[-1] - G[j]
                if j + j-i < n:
                    if s[j+(j-i)] == 'G':
                        ans -= 1
    else:
        for j in range(i+1,n):
            if s[j] == 'B':
                ans += R[-1] - R[j]
                if j + (j-i) < n:
                    if s[j+(j-i)] == 'R':
                        ans -= 1
            elif s[j] == 'R':
                ans += B[-1] - B[j]
                if j + j-i < n:
                    if s[j+(j-i)] == 'B':
                        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000007

def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b


def main():
    N = int(readline())
    S = readline().rstrip().decode()
    rn = 0
    gn = 0
    bn = 0
    R = [0]
    G = [0]
    B = [0]

    for i in range(N):
        if S[i]=="R":
            rn+=1
        if S[i]=="G":
            gn+=1
        if S[i]=="B":
            bn+=1
        R.append(rn)
        G.append(gn)
        B.append(bn)
    ans = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            if S[i]!=S[j]:
                if "R"!=S[i] and "R"!=S[j]:
                    ans += R[N]-R[j]
                    if j+(j-i) < N:
                        if S[j+(j-i)]=="R":
                            ans-=1
                elif "G"!=S[i] and "G"!=S[j]:
                    ans += G[N]-G[j]
                    if j+(j-i) < N:
                        if S[j+(j-i)]=="G":
                            ans-=1
                elif "B"!=S[i] and "B"!=S[j]:
                    ans += B[N]-B[j]
                    if j+(j-i) < N:
                        if S[j+(j-i)]=="B":
                            ans-=1
        
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip("\n")
    col = {"R": 0, "G": 1, "B": 2}
    B = [[0, 0, 0] for _ in range(N)]
    B[N-1][col[S[N-1]]] = 1
    for i in reversed(range(N-1)):
        for j in range(3): B[i][j] = B[i+1][j]
        B[i][col[S[i]]] += 1

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
acc0 = [0]
acc1 = [0]
acc2 = [0]

for i in range(N):
    if S[i]=='R':
        acc0.append(acc0[-1]+1)
        acc1.append(acc1[-1])
        acc2.append(acc2[-1])
    elif S[i]=='G':
        acc0.append(acc0[-1])
        acc1.append(acc1[-1]+1)
        acc2.append(acc2[-1])
    else:
        acc0.append(acc0[-1])
        acc1.append(acc1[-1])
        acc2.append(acc2[-1]+1)
        
ans = 0

for i in range(N):
    for j in range(i+1, N):
        if S[i]==S[j]:
            continue
        
        if (S[i]=='R' and S[j]=='G') or (S[i]=='G' and S[j]=='R'):
            ans += acc2[N]-acc2[j+1]
            
            if j+(j-i)<N and S[j+(j-i)]=='B':
                ans -= 1
                
        elif (S[i]=='R' and S[j]=='B') or (S[i]=='B' and S[j]=='R'):
            ans += acc1[N]-acc1[j+1]
            
            if j+(j-i)<N and S[j+(j-i)]=='G':
                ans -= 1
                
        elif (S[i]=='G' and S[j]=='B') or (S[i]=='B' and S[j]=='G'):
            ans += acc0[N]-acc0[j+1]
            
            if j+(j-i)<N and S[j+(j-i)]=='R':
                ans -= 1

print(ans)

Submission status: Accepted

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

count = {"R":0,"G":0,"B":0}
for c in s:
    count[c] += 1

r,g,b = count.values()
ans = r*g*b
for i in range(1,(n-1)//2+1):
    for rgb in zip(s,s[i:],s[i*2:]):
        if len(set(rgb)) == 3:
            ans -=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
red = []
green = []
blue = [False for _ in range(n)]
b = 0
for i,x in enumerate(s):
    if x == "R":
        red.append(i)
    if x == "G":
        green.append(i)
    if x == "B":
        blue[i] = True
        b += 1

ans = 0
for i in red:
    for j in green:
        p = 0
        if 0<=2*j-i<n and blue[2*j-i]:
            p += 1
        if 0<=2*i-j<n and blue[2*i-j]:
            p += 1
        if (i+j)%2 == 0 and blue[(i+j)//2]:
            p += 1
        ans += b-p
print(ans)