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
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from bisect import bisect_left
def resolve():
    N = ir()
    S = sr()
    R = []
    G = []
    B = []
    for i in range(N):
        if S[i] == 'R':
            R.append(i+1)
        elif S[i] == 'G':
            G.append(i+1)
        else:
            B.append(i+1)
    ans = len(R)*len(G)*len(B)
    for r in R:
        for g in G:
            if abs(r+g)%2 == 0:
                if abs(r+g)//2 in B:
                    ans -= 1
    for r in B:
        for g in G:
            if abs(r+g)%2 == 0:
                if abs(r+g)//2 in R:
                    ans -= 1
    for r in R:
        for g in B:
            if abs(r+g)%2 == 0:
                if abs(r+g)//2 in G:
                    ans -= 1
            # for b in B:
            #     rg = abs(r-g)
            #     gb = abs(g-b)
            #     br = abs(b-r)
            #     if rg != gb and gb != br and br != rg:
            #         ans += 1
                # i = min(r, g, b)
                # k = max(r, g, b)
                # a = k-i
                # if a != 2*r and a != 2*g and a != 2*b:
                #     ans += 1
    # for n in R:
    #     # x = bisect_left(G, n)
    #     for i in G:
    #         a = max(n, i)
    #         b = min(n, i)
    #         x = bisect_left(B, a)
    #         ans += len(B[x:])
    #         if 2*a-b in B:
    #             ans -= 1
    # for n in R:
    #     # x = bisect_left(B, n)
    #     for i in B:
    #         a = max(n, i)
    #         b = min(n, i)
    #         x = bisect_left(G, a)
    #         ans += len(G[x:])
    #         if 2*a-b in G:
    #             ans -= 1
    # # for n in G:
    # #     x = bisect_left(R, n)
    # #     for i in R[x:]:
    # #         x = bisect_left(B, i)
    # #         ans += len(B[x:])
    # #         if 2*i-n in B:
    # #             ans -= 1
    # for n in G:
    #     # x = bisect_left(B, n)
    #     for i in B:
    #         a = max(n, i)
    #         b = min(n, i)
    #         x = bisect_left(R, a)
    #         ans += len(R[x:])
    #         if 2*a-b in R:
    #             ans -= 1
    # for n in B:
    #     x = bisect_left(R, n)
    #     for i in R[x:]:
    #         x = bisect_left(G, i)
    #         ans += len(G[x:])
    #         if 2*i-n in G:
    #             ans -= 1
    # for n in B:
    #     x = bisect_left(G, n)
    #     for i in G[x:]:
    #         x = bisect_left(R, i)
    #         ans += len(R[x:])
    #         if 2*i-n in R:
    #             ans -= 1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
S = input()

d = defaultdict(int)
for c in S:
    d[c] += 1
plus = d['R'] * d['G'] * d['B']

minus = 0
for j in range(1, N - 1):
    for l in range(1, N):
        i, k = j - l, j + l
        if i < 0 or k > N - 1:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            minus += 1

print(plus - minus)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import bisect

N=input()
S=input()

R=[]
G=[]
B=[]
for i in range(len(S)):
    if S[i]=="R":
        R.append(i)
    elif S[i]=="G":
        G.append(i)
    else:
        B.append(i)

ans=0

def calc(lis0,lis1,lis2):
    temp=0
    for l0 in lis0:
        for l1 in lis1:
            if l1<l0:
                continue
            start=bisect.bisect_right(lis2,l1)
            temp+=len(lis2)-start
            index=bisect.bisect_left(lis2,2*l1-l0)
            #if 2*l1-l0 in lis2:
            #    temp-=1
            if index!=len(lis2):
                if lis2[index]==2*l1-l0:
                    temp-=1
    return temp

ans=calc(R,G,B)+calc(R,B,G)+calc(G,R,B)+calc(G,B,R)+calc(B,R,G)+calc(B,G,R)
            
print(ans)

Submission status: Accepted

Solution code:
# %%time
from collections import Counter, deque
n = int(input())
s = input()


# n = 4000
# np.random.seed(1)
# s = np.random.randint(0, 3, n)
# s = (s)

c = Counter(s)
c = list(c.values())
if len(c) == 3:
    ans = c[0] * c[1] * c[2]
else:
    ans = 0
# print(ans)
if ans > 0:
    for k in range(n):
        for a in range(1, (n - k)//2 + 1):
            if k + 2 * a >= n:
                continue
            x, y,  = s[k], s[k + a]
            
            if x != y:
                z = s[k + 2 * a]
                if y != z:
                    if z != x:
                        ans -= 1

print(ans)

Submission status: Accepted

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

check = dict()
def get_pattern2(i, j):
    a = s[i]
    b = s[j]
    total = 0
    check_str = ""
    if a == "R" or b == "R":
        check_str += "R"
    if a == "G" or b == "G":
        check_str += "G"
    if a == "B" or b == "B":
        check_str += "B"

    for k in range(j+1, n):
        if check_str+str(k) in check:
            total += check[check_str+str(k)]
            break
        if a != s[k] and b != s[k]:
            total += 1
    check[check_str+str(j+1)] = total
    return total

def get_pattern(i):
    a = s[i]
    total = 0
    for j in range(i+1, n):
        if a+str(j) in check:
            total += check[a+str(j)]
            break
        if a != s[j]:
            total += get_pattern2(i, j)
    check[a+str(i+1)] = total

    # k-j = i-jなものをぬく
    for j in range(i+1, n):
        k = j + j - i
        if k >= n:
            break
        if a != s[k] and s[j] != s[k] and a != s[j]:
            total -= 1
    return total

total = 0
for i in range(n-1, -1, -1):
    total += get_pattern(i)
print(total)

Submission status: Accepted

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

r, g, b = 0, 0, 0
for si in s:
    if si == "R":
        r += 1
    elif si == "G":
        g += 1
    else:
        b += 1
        
ans = r * g * b

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
#N, M = map(int, input().split())
#A = list(map(lambda x: int(x)*(-1), input().split()))
#A = [int(input()) for i in range(N)]
#C = [list(map(int, input().split())) for i in range()]
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)
answer = len(R)*len(G)*len(B)
hiku = 0

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


answer -= hiku
print(answer)

Submission status: Accepted

Solution code:
def solve(n,s,l1,l2,l3):
  ans = len(l1)*len(l2)*len(l3)

  for a in l1:
    for b in l2:
      if a < b:
        if 2*b-a in l3:
          ans -= 1
        if 2*a-b in l3:
          ans -= 1
        if (b-a-1)%2==0:
          continue
        else:
          if (b-a)%2 == 0 and (b-a)/2 + a in l3:
            ans -= 1
      else:
        if 2*a-b in l3:
          ans -= 1
        if 2*b-a in l3:
          ans -= 1
        if (a-b-1)%2==0:
          continue
        else:
          if (a-b)%2 == 0 and (a-b)/2 + b in l3:
            ans -= 1
  return ans



if __name__ == "__main__":
  n= int(input())
  s = input()
  r_list = set()
  g_list = set()
  b_list = set()
  r_count = 0
  g_count = 0
  b_count = 0
  for i, str in enumerate(s):
    if str == "R":
      r_list.add(i+1)
      r_count += 1
    elif str == "G":
      g_list.add(i+1)
      g_count += 1
    else:
      b_list.add(i+1)
      b_count += 1

  if r_count <= g_count and r_count <= b_count:
    l1 = r_list
    if g_count <= b_count:
      l2 = g_list
      l3 = b_list
    else:
      l2 = b_list
      l3 = g_list
  elif g_count <= r_count and g_count <= b_count:
    l1 = g_list
    if r_count <= b_count:
      l2 = r_list
      l3 = b_list
    else:
      l2 = b_list
      l3 = r_list
  elif b_count <= g_count and b_count <= r_count:
    l1 = b_list
    if g_count <= r_count:
      l2 = g_list
      l3 = r_list
    else:
      l2 = r_list
      l3 = g_list

  print(solve(n, s, l1,l2,l3))

Submission status: Accepted

Solution code:
from sys import stdin, stdout
def main():
    N=int(stdin.readline())
    S=stdin.readline().rstrip()
    R, G, B = set(), set(), set()
    for i, c in enumerate(S):
        if c == 'R':
            R.add(i)
        elif c == 'G':
            G.add(i)
        else:
            B.add(i)
    cnt, total = 0, len(R) * len(G) * len(B)
    for ri in R:
        for gi in G:
            if abs(ri-gi)+gi in B:
                cnt += 1
            if abs(ri-gi)+ri in B:
                cnt += 1
    for ri in G:
        for gi in B:
            if abs(ri-gi)+gi in R:
                cnt += 1
            if abs(ri-gi)+ri in R:
                cnt += 1
    for ri in R:
        for gi in B:
            if abs(ri-gi)+gi in G:
                cnt += 1
            if abs(ri-gi)+ri in G:
                cnt += 1

    stdout.write(str(total-cnt)+"\n")

main()

Submission status: Accepted

Solution code:
S = input()
S = list(input())
S_len = len(S)
ans = 0
i = 0
for _ in range(S_len):
  if S[0] == 'R':
    ans += S[1:].count('B') * S[1:].count('G')
    for j in range(int(len(S)/2+1)):
      try:
        if S[j+1] != S[j*2+2] and S[j*2+2] !='R' and S[j+1] !='R':
          ans-=1
      except:
        pass
  if S[0] == 'B':
    ans += S[1:].count('R') * S[1:].count('G')
    for j in range(int(len(S)/2+1)):
      try:
        if S[j+1] != S[j*2+2] and S[j*2+2] !='B' and S[j+1] !='B':
          ans-=1
      except:
        pass
  if S[0] == 'G':
    ans += S[1:].count('B') * S[1:].count('R')
    for j in range(int(len(S)/2+1)):
      try:
        if S[j+1] != S[j*2+2] and S[j*2+2] !='G' and S[j+1] !='G':
          ans-=1
      except:
        pass
  S  = S[1:]
print(ans)

Submission status: Accepted

Solution code:
import sys

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

rs = []
gs = []
bs = []

for i in range(n):
  if s[i] == "R":
    rs.append(i)
  elif s[i] == "G":
    gs.append(i)
  elif s[i] == "B":
    bs.append(i)

def binary(lst, d):
  low = 0
  high = len(lst) - 1
  while low <= high:
    mid = (low + high) // 2
    if lst[mid] == d:
      return True
    elif lst[mid] < d:
      low = mid + 1
    else:
      high = mid - 1
  return False

ans = len(rs)*len(gs)*len(bs)
if len(bs) == 0:
  print(0)
  sys.exit()
for i in range(len(rs)):
  for j in range(len(gs)):
    dis = abs(rs[i] - gs[j])
    if (rs[i] + gs[j])%2 == 0:
      can1 = abs(rs[i] + gs[j])//2
      if binary(bs, can1):
      	ans -= 1
    if max(rs[i], gs[j]) + dis <= bs[-1]:
      can2 = max(rs[i], gs[j]) + dis
      if binary(bs, can2):
      	ans -= 1
    if min(rs[i], gs[j]) - dis > 0:
      can3 = min(rs[i], gs[j]) - dis
      if binary(bs, can3):
      	ans -= 1
        
print(ans)

Submission status: Accepted

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

rs = {}
gs = {}
bs = {}

for i, e in enumerate(s):
  if e == 'R':
    rs[i] = ''
  if e == 'G':
    gs[i] = ''
  if e == 'B':
    bs[i] = ''
    
saidai = len(rs) * len(gs) * len(bs)
if saidai == 0:
  print('0')
else:
  a = max(bs.keys())
  b = min(bs.keys())
  for i in rs.keys():
    for j in gs.keys():
      mi = i if i < j else j
      ma = j if i < j else i
      p = [mi - (ma - mi), mi + (ma - mi)/2, ma + (ma - mi)]
      for e in p:
        if e%1 != 0 or e < b or e > a:
          continue
        if e in bs:
          saidai -= 1
  print(int(saidai))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
T = {'R', 'G', 'B'}
sum_R, sum_G, sum_B = [0], [0], [0]
 
for i in S:
    sum_R.append(i=='R')
    sum_G.append(i=='G')
    sum_B.append(i=='B')
    
for i in range(1, N+1):
    sum_R[i] = sum_R[i-1] + sum_R[i]
    sum_G[i] = sum_G[i-1] + sum_G[i]
    sum_B[i] = sum_B[i-1] + sum_B[i]
    
dict_RGB = {'R':sum_R, 'G':sum_G, 'B':sum_B}
 
for i in range(N-2):
    s_i = S[i]
    for j in range(i+1, N-1):
        s_j = S[j]
        if s_i == s_j:
            continue
        
        s_k = list(T - set((s_i, s_j)))[0]
        
        sum_s_k = dict_RGB[s_k]
        ans = ans + sum_s_k[-1] - sum_s_k[j]
        if (2 * j - i < N) and (S[2*j - i]==s_k):
            ans -= 1
        
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
strings = input()
r_array, g_array, b_array = list(), list(), list()

sums = [0, 0, 0]


def counter(s):
    if s == "R":
        sums[0] += 1
    elif s == "G":
        sums[1] += 1
    else:
        sums[2] += 1
    r_array.append(sums[0])
    g_array.append(sums[1])
    b_array.append(sums[2])


for s in strings:
    counter(s)

ret = 0
for i in range(n):
    s = strings[i]
    _r, _g, _b = r_array[i], g_array[i], b_array[i]
    r_, g_, b_ = sums[0] - _r, sums[1] - _g, sums[2] - _b
    if s == "R":
        ret += _g * b_ + _b * g_
    elif s == "G":
        ret += _r * b_ + _b * r_
    else:
        ret += _r * g_ + _g * r_

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
s = input()
c = Counter({'R': 0,'G': 0, 'B': 0})
c.update(s)
x, y, z = c.values()
print(x * y * z - sum(s[i] != s[(i + j) // 2] != s[j] != s[i]
                      for i in range(n) for j in range(i + 2, n, 2)))

Submission status: Accepted

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

    rc0 = [0] * N
    gc0 = [0] * N
    bc0 = [0] * N

    rc = [0] * N
    gc = [0] * N
    bc = [0] * N

    rlist = []
    glist = []
    blist = []

    if True:
        i = N - 1
        if S[i] == 'R':
            rc[i] = 1
            rc0[i] = 1
        elif S[i] == 'G':
            gc[i] = 1
            gc0[i] = 1
        elif S[i] == 'B':
            bc[i] = 1
            bc0[i] = 1

    for i in range(N - 2, -1, -1):
        if S[i] == 'R':
            rc[i] += 1
            rc0[i] = 1
            rlist.append(i)
        elif S[i] == 'G':
            gc[i] += 1
            gc0[i] = 1
            glist.append(i)
        else:
            bc[i] += 1
            bc0[i] = 1
            blist.append(i)

    for i in range(N - 2, -1, -1):
        rc[i] += rc[i + 1]
        gc[i] += gc[i + 1]
        bc[i] += bc[i + 1]

    def count(rlist, glist, bc, bc0):
        v = 0

        for i in rlist:
            for j in glist:
                if i >= j:
                    break
                k = 2 * j - i
                if k < N:
                    v += bc[j + 1] - bc0[k]
                else:
                    v += bc[j + 1]
        return v

    rgb = 0
    rgb += count(rlist, glist, bc, bc0)
    rgb += count(rlist, blist, gc, gc0)
    rgb += count(glist, rlist, bc, bc0)
    rgb += count(glist, blist, rc, rc0)
    rgb += count(blist, rlist, gc, gc0)
    rgb += count(blist, glist, rc, rc0)
    print(rgb)


main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
R =[]
G = []
B = []
lr = 0
lg = 0
lb = 0
ncount = 0
for i in range(N):
    if S[i] == "R":
        R.append(i)
        lr+=1
    elif S[i] == "G":
        G.append(i)
        lg+=1
    else:
        B.append(i)
        lb+=1
    if i < N/2:
        for j in range(i+1):
            if S[i-j]!=S[i]:
                if S[i-j] != S[i+j]:
                    if S[i+j] != S[i]:
                        ncount+=1
    else:
        for j in range(N-i):
                if S[i-j]!=S[i]:
                    if S[i-j] != S[i+j]:
                        if S[i+j] != S[i]:
                            ncount+=1
print(lr*lg*lb - ncount)

Submission status: Accepted

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

def im(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
R = im(s, "R")
G = im(s, "G")
B = im(s, "B")

ext = 0
if n >= 3:
    for i in range((n-3)//2+1):
        for j in range(n-(3+2*i)+1):
            if s[j] != s[j+i+1] and s[j] != s[j+2*(i+1)] and s[j+i+1] != s[j+2*(i+1)]:
                ext += 1

ans = len(R)*len(G)*len(B) - ext
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n = int(input()) # 入力が1つ
s = input()
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
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

def bs(nums, target):
    l = 0
    r = len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return True
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return False

def solution(t1, t2, t3):
    ans = 0
    if len(t1) < 1 or len(t2) < 1 or len(t3) < 1:
        return ans
    for i in range(len(t2)):
        num = t2[i]
        left = bisect_left(t1, num)
        right = bisect_right(t3, num)
        ans += left * (len(t3) - right)

    for i in t1:
        for j in t3:
            if i < j:
                if (i + j) % 2 == 0 and bs(t2, (i + j) // 2):
                    ans -= 1
    return ans

ans = 0
ans += solution(r, g, b)
ans += solution(r, b, g)
ans += solution(g, r, b)
ans += solution(g, b, r)
ans += solution(b, r, g)
ans += solution(b, g, r)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
#h  = list(map(int, input().split()))
#h, w = list(map(int, input().split()))

#j-i=k-jではない 2j=k+i i=2j-k

s = input()
count = 0

"""
for i in range(n):
    for j in range(i+1, n):
        if s[i]!=s[j]:    
            for k in range(j+1, n):
                if j-i!=k-j:
                    if s[i]!=s[k] and s[j]!=s[k]:
                        count += 1
"""
for i in range(n):
    a = s[i:]
    if s[i]=="R":
        point = a.count("G")*a.count("B")
    elif s[i]=="G":
        point = a.count("R")*a.count("B")
    else:
        point = a.count("R")*a.count("G")
    count += point

#j-i=k-jではない 2j=k+i i=2j-k
#rgb

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


print(count-kom)

Submission status: Accepted

Solution code:
N=int(input())
A=input()
c=0
B1B=0
B1R=0
B1G=0
if A[0]=="B":
 B1B+=1
elif A[0]=="R":
 B1R+=1
else:
 B1G+=1
for i in range(N-2):
 B2=A[i+1]
 for k in range(N-i-2):
  B3=A[i+2+k]
  if (B2=="B" and B3=="R")or (B2=="R" and B3=="B"):
   c+=B1G
   if (i+2+k)<=(i+1)*2:
    if A[(i+1)*2-(i+2+k)]=="G":
     c-=1
  if (B2=="G" and B3=="R")or (B2=="R" and B3=="G"):
   c+=B1B
   if (i+2+k)<=(i+1)*2:
    if A[(i+1)*2-(i+2+k)]=="B":
     c-=1
  if (B2=="B" and B3=="G")or (B2=="G" and B3=="B"):
   c+=B1R
   if (i+2+k)<=(i+1)*2:
    if A[(i+1)*2-(i+2+k)]=="R":
     c-=1
 if B2=="B":
  B1B+=1
 elif B2=="R":
  B1R+=1
 else:
  B1G+=1
print(c)

Submission status: Accepted

Solution code:
# import sys 
# try:
#     sys.stdin = open('input.txt', 'r') 
#     sys.stdout = open('output.txt', 'w')
# except:
#     pass

n = int(input())
s = input()
r =[]
g = []
b = []
for i in range(n):
	if s[i] == 'R':
		r.append(i)
	elif s[i] == 'G':
		g.append(i)
	else:
		b.append(i)
temp2 = []
for i in r:
	for j in g:
		temp = []
		if (i+j)%2 == 0:
			temp.append((i+j)//2)
		temp.append(min(i,j)-abs(i-j))
		temp.append(max(i,j)+abs(i-j))
		temp2.append(temp)
l = len(b)
d = {}
for i in b:
	d[i] = 1
res = 0
for i in temp2:
	x = l
	for j in i:
		if j in d:
			x -= 1
	res += x
print(res)

Submission status: Accepted

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

R, G, B = [], [], []
for i, c in enumerate(s):
  if c == 'R': R.append(i)
  elif c == 'G': G.append(i)
  else: B.append(i)

ans = 0
for r in R:
  for g in G:
    if r < g: x, y = r, g
    else: x, y = g, r

    ans += len(B)
    if x*2 - y >= 0:
      if s[x*2 - y] == 'B': ans -= 1
    if (x + y) % 2 == 0:
      if s[(x+y)//2] == 'B': ans -= 1
    if y*2 - x < len(s):
      if s[y*2 - x] == 'B': ans -= 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
r_list = []
g_list = []
b_list = []

for i in range(n):
  if s[i] == "R":
    r_list.append(i)
  elif s[i] == "G":
    g_list.append(i)
  elif s[i] == "B":
    b_list.append(i)
    
judge = n%2
if judge == 1:
  lim = (n-3)//2 + 1
elif judge == 0:
  lim = (n-4)//2 + 1

pena = 0

for i in range(1,lim+1):
  for j in range(n-2*i):
    if (s[j] != s[j+i]) and (s[j] != s[j+2*i]) and (s[j+i] != s[j+2*i]):
      pena = pena + 1

print(len(r_list)*len(g_list)*len(b_list) - pena)

Submission status: Accepted

Solution code:

"""
K = int(input())

def gcd(a, b): # 最大公約数
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a % b
    return a # int
ans = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            d = gcd(gcd(i,j),k)
            if i==j==k:
                ans += d
            elif i==j or j== k or k==i:
                ans += 3*d
            else:
                ans += 6*d
print(ans)
"""
N = int(input())
S = input()
R = []
G = []
B = []
import bisect
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 rr in R:
    for gg in G:
        
        r = min(rr,gg)
        g = max(rr,gg)
        if 2*r-g>=0:
            id = bisect.bisect_left(B,2*r-g)
            if id < len(B) and 2*r-g == B[id]:
                ans -=1
        
        if 2*g-r < N:
            id = bisect.bisect_left(B,2*g-r)
            if id < len(B) and 2*g-r == B[id]:
                ans -=1
        
        if (g+r)%2==0:
            id = bisect.bisect_left(B,(g+r)//2)
            if id < len(B) and (g+r)//2 == B[id]:
                ans -= 1
        ans += len(B)
        
print(ans)

Submission status: Accepted

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

max_cnt = s.count('R')*s.count('G')*s.count('B')

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

print(max_cnt-tmp)

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
s = input()

r_acc = [0] + list(accumulate([int(s[i] == 'R') for i in range(n)]))
g_acc = [0] + list(accumulate([int(s[i] == 'G') for i in range(n)]))
b_acc = [0] + list(accumulate([int(s[i] == 'B') for i in range(n)]))

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        si = s[i]
        sj = s[j]
        if si == sj:
            continue
        if (si == 'R' and sj == 'G') or (si == 'G' and sj == 'R'):
            ans += b_acc[n] - b_acc[j]
            if n >= j + j - i + 1:
                ans -= b_acc[j + j - i + 1] - b_acc[j + j - i]
        elif (si == 'R' and sj == 'B') or (si == 'B' and sj == 'R'):
            ans += g_acc[n] - g_acc[j]
            if n >= j + j - i + 1:
                ans -= g_acc[j + j - i + 1] - g_acc[j + j - i]
        else:
            ans += r_acc[n] - r_acc[j]
            if n >= j + j - i + 1:
                ans -= r_acc[j + j - i + 1] - r_acc[j + j - i]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
list_S = list(input())
list_R = []
list_B = []
list_G = []
ans = 0
for i, c in enumerate(list_S):
    if c == "R":
        list_R.append(i+1)
    if c == "B":
        list_B.append(i+1)
    if c == "G":
        list_G.append(i+1)
set_R = set(list_R)
set_G = set(list_G)
set_B = set(list_B)
cnt = 0
for i in list_R:
    for j in list_G:
        max_value = max(i, j)
        min_value = min(i, j)
        d = (max_value - min_value)
        if d % 2 == 0:
            if max_value-d//2 in set_B:
                cnt += 1

        if max_value+d in set_B:
            cnt += 1
        if min_value-d in set_B:
            cnt += 1
        ans += len(set_B)

print(ans-cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
r = [0]*n
g = [0]*n
b = [0]*n
for i in range(n):
    if s[i]=='R':
        r[i] = 1
    elif s[i] == 'G':
        g[i] = 1
    elif s[i] == 'B':
        b[i] = 1

r_cum = [0]*n
g_cum = [0]*n
b_cum = [0]*n

x = y = z = 0
i = n-1
while i>=0:
    if r[i]==1:
        x+=1
    if g[i]==1:
        y+=1
    if b[i]==1:
        z+=1
    r_cum[i] = x
    g_cum[i] = y
    b_cum[i] = z
    i-=1
s = 0
for i in range(n):
    for j in range(i+1,n):
        #RGB
        if r[i]==1 and g[j]==1:
            if j+1<n and 2*j-i<n and b[2*j-i] == 1:
                s = s + (b_cum[j+1]-1)
            elif j+1<n:
                s = s + b_cum[j+1]
        #RBG
        if r[i]==1 and b[j]==1:
            if j+1<n and 2*j-i<n and g[2*j-i] == 1:
                s = s + (g_cum[j+1]-1)
                #print(i,j,b_cum[j+1]-1)
            elif j+1<n:
                s = s + g_cum[j+1]
                #print(i,j,b_cum[j+1])
        #GBR
        if g[i]==1 and b[j]==1:
            if j+1<n and 2*j-i<n and r[2*j-i] == 1:
                s = s + (r_cum[j+1]-1)
                #print(i,j,b_cum[j+1]-1)
            elif j+1<n:
                s = s + r_cum[j+1]
                #print(i,j,b_cum[j+1])
        #GRB
        if g[i]==1 and r[j]==1:
            if j+1<n and 2*j-i<n and b[2*j-i] == 1:
                s = s + (b_cum[j+1]-1)
                #print(i,j,b_cum[j+1]-1)
            elif j+1<n:
                s = s + b_cum[j+1]
                #print(i,j,b_cum[j+1])
        if b[i]==1 and r[j]==1:
            if j+1<n and 2*j-i<n and g[2*j-i] == 1:
                s = s + (g_cum[j+1]-1)
                #print(i,j,b_cum[j+1]-1)
            elif j+1<n:
                s = s + g_cum[j+1]
                #print(i,j,b_cum[j+1])
        if b[i]==1 and g[j]==1:
            if j+1<n and 2*j-i<n and r[2*j-i] == 1:
                s = s + (r_cum[j+1]-1)
                #print(i,j,b_cum[j+1]-1)
            elif j+1<n:
                s = s + r_cum[j+1]
                #print(i,j,r_cum[j+1])
print(s)

Submission status: Accepted

Solution code:
n=int(input())
a=list(input())
r=[0]*n
g=[0]*n
b=[0]*n
for i in range(n):
  if i==0:
    if a[n-1-i]=='R':
      r[n-1-i]=1
    elif a[n-1-i]=='G':
      g[n-1-i]=1
    else:
      b[n-1-i]=1
  else:
    if a[n-1-i]=='R':
      r[n-1-i]=r[n-i]+1
      g[n-1-i]=g[n-i]
      b[n-1-i]=b[n-i]
    elif a[n-1-i]=='G':
      r[n-1-i]=r[n-i]
      g[n-1-i]=g[n-i]+1
      b[n-1-i]=b[n-i]
    else:
      r[n-1-i]=r[n-i]
      g[n-1-i]=g[n-i]
      b[n-1-i]=b[n-i]+1

count=0
if n==1:
  print(0)
elif n==2:
  print(0)
else:
  for i in range(n-2):
    for j in range(i+1,n-1):
      if a[i]!=a[j] and 2*j-i<n and a[i]!=a[2*j-i] and a[j]!=a[2*j-i]:
        if a[i]!='R' and a[j]!='R':
          count+=r[j+1]-1
        elif a[i]!='G' and a[j]!='G':
          count+=g[j+1]-1
        else:
          count+=b[j+1]-1
      elif a[i]!=a[j]:
        if a[i]!='R' and a[j]!='R':
          count+=r[j+1]
        elif a[i]!='G' and a[j]!='G':
          count+=g[j+1]
        else:
          count+=b[j+1]
  print(count)

Submission status: Accepted

Solution code:
from itertools import product as pro

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

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

length = max(len(r), len(g), len(b))
for i, j, k in [(r, g, b), (g, b, r), (b, r, g)]:
    if length == len(i):
        max1 = set(i)
        min1, min2 = j, k

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

print(cnt)

Submission status: Accepted

Solution code:
n = int(input().strip())
s = '_' + input().strip()
s += ''.join(['_'] * 10 ** 5)
r = []
g = []
b = []
for i in range(1, n + 1):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    elif s[i] == 'B':
        b.append(i)

le = len(b)
ans = len(r) * len(g) * le
for x in r:
    for y in g:
        if (x + y) % 2 == 0 and s[(x + y) // 2] == 'B':
            ans -= 1
        if (1 <= (2 * x - y) and s[2 * x - y] == 'B'):
            ans -= 1
        if (1 <= (2 * y - x) and s[2 * y - x] == 'B'):
            ans -= 1
print(ans)

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    s = input()
    dic = {'R':[],'G':[],'B':[]}
    for i in range(n):
        if s[i]== 'R':
            dic['R'].append(i)
        elif s[i]== 'G':
            dic['G'].append(i)
        else:
            dic['B'].append(i)
    cnt = len(dic['R'])*len(dic['G'])*len(dic['B'])
    for i in range(1,n//2+1):
        for j in range(n-2*i):
            if s[j]!=s[j+i] and s[j+i] != s[j+i+i] and s[j]!=s[j+i+i]:
                cnt -=1
    print(cnt)
     
            
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
s = input().strip()

if ('R' not in s) or ('G' not in s) or ('B' not in s):
    print(0)
    sys.exit(0)

from collections import deque

index_cache = {'R': deque(), 'G': deque(), 'B': deque()}
for i, v in enumerate(s):
    index_cache[v].append(i)

ans = 0
for i, v in enumerate(s):
    index_cache[v].popleft()

    v2, v3 = set('RGB') - set(v)
    if len(index_cache[v2]) == 0 or len(index_cache[v3]) == 0:
        break

    i2, i3 = index_cache[v2][0], index_cache[v3][0]
    ans += len(index_cache[v2]) * len(index_cache[v3])

    if i2 < i3:
        for i4 in index_cache[v2]:
            if i4 + (i4 - i) < n and s[i4 + (i4 - i)] == v3:
                ans -= 1
            if (i + i4) % 2 == 0 and s[(i + i4) // 2] == v3:
                ans -= 1
    else:
        for i5 in index_cache[v3]:
            if i5 + (i5 - i) < n and s[i5 + (i5 - i)] == v2:
                ans -= 1
            if (i + i5) % 2 == 0 and s[(i + i5) // 2] == v2:
                ans -= 1

print(ans)

Submission status: Accepted

Solution code:
import math

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

def Word(i, a, b):
    if S[i] != S[i + a] and S[i] != S[i + a + b] and S[i + a] != S[i + a + b]:
        return True
    else:
        return False

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

ans = R * G * B
for i in range(0, N - 1):
    for a in range(1, math.ceil(N / 2)):
        if i + a * 2 >= N:
            break
        if S[i] != S[i + a] and S[i] != S[i + a * 2] and S[i + a] != S[i + a * 2]:
            ans -= 1

print(ans)