Problem:


Score : 400 points

Problem Statement

We have a string S of length N consisting of R, G, and B.

Find the number of triples (i,~j,~k)~(1 \leq i < j < k \leq N) that satisfy both of the following conditions:

S_i \neq S_j, S_i \neq S_k, and S_j \neq S_k.

j - i \neq k - j.

Constraints

1 \leq N \leq 4000

S is a string of length N consisting of R, G, and B.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of triplets in question.

Sample Input 1

4
RRGB

Sample Output 1

1

Only the triplet (1,~3,~4) satisfies both conditions. The triplet (2,~3,~4) satisfies the first condition but not the second, so it does not count.

Sample Input 2

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

Sample Output 2

1800



Sample input:
4
RRGB


Sample output:
1

Submission status: Time Limit Exceeded

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

for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if s[j] != s[i]:
                for k in range(j + 1, len(s)):
                    if s[k] != s[j] and s[k] != s[i] and j - i != k - j:
                        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
f=0
ijk = list()
for i in range(N):
    for j in range(N):
        for k in range(N):
            if(i<j<k):
                if(S[i]!=S[j] and
                    S[i]!=S[k] and
                    S[j]!=S[k]):
                        ijk.append([i+1,j+1,k+1])
# print(ijk)
for i in range(len(ijk)):
    if(ijk[i][1]-ijk[i][0] != ijk[i][2]-ijk[i][1]):
        f+=1
print(f)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
S = input()
C = list(itertools.combinations_with_replacement(range(1, N + 1), 3))
count = 0
for i, j, k in C:
    if (i != 2 * j - k) and (S[i - 1] != S[j - 1] and S[i - 1] != S[k - 1] and S[j - 1] != S[k - 1]):
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
S = list(input())
R = []
G = []
B = []
total = 0

for a in range(0,K):
  if S[a]=="R":
    R.append(a)
  elif S[a]=="G":
    G.append(a)
  else :
    B.append(a)

for a in R:
  for b in G:
    for c in B:
      tmp = [a,b,c]
      tmp.sort()
      if tmp[1]-tmp[0] != tmp[2]-tmp[1]:
        total += 1
        #print(tmp)
print(total)

Submission status: Time Limit Exceeded

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

Ans = 0
for i in range(N):
  s = S[i]
  a = 0
  b = 0
  L = ["R","G","B"]
  L.remove(s)
  for j in range(i+1,N):
    t = S[j]
    if s != t:
      if t == L[0]:
        a +=1
      else:
        b +=1
  Ans += a*b

for i in range(N):
  n = min(N,(N+i-1)//2 +1)
  for j in range(i+1,n):
    s = S[i]
    t = S[j]
    if s != t:
      k = 2*j-i
      if k <= N-1:
        u = S[k]
        if t != u and u != s:
          Ans -=1
print(Ans)

Submission status: Time Limit Exceeded

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

answer = 0

for a in range(N):
  i = S[a]
  for b in range(N-a-1):
    j = S[b+a+1]
    if i == j:
      pass
    else:
      for c in range(N-a-b-2):
        k = S[c+a+b+2]
        if i == k or j == k:
          pass
        else:
          if (b+a+1) - a != (c+a+b+2) - (b+a+1):
            answer += 1
  	      
else:
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(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

for r in R:
  for g in G:
    for b in B:
      rgb = [r,g,b]
      rgb.sort()
      if rgb[1] - rgb[0] != rgb[2] - rgb[1]:
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
count = 0
len = len(s)

for i in range(len):
        for j in range(i, len):
            if s[j] != s[i]:
                for k in range(j, len):
                    if s[k] != s[j] and s[k] != s[i] and j - i != k - j:
                        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in r:
    x=i

    for j in g:
        y=j

        if 2*x-y in b:
            k+=1
        if 2*y-x in b:
            k+=1
        if (x+y)/2 in b:
            k+=1

print(A*B*C-k)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	S = input()
	S = S[:-1]

	R = []
	G = []
	B = []
	for i,val in enumerate(S):
		if val == "R":
			R.append(i)
		elif val == "G":
			G.append(i)
		else:
			B.append(i)

	ans = 0
	for i,val in enumerate(R):
		tmp = bisect_right(G, val)
		if len(G) == tmp:
			break

		for j in range(tmp,len(G)):
			tmptmp = bisect_right(B, G[j])
			if len(B) == tmptmp:
				break

			blacks = G[j] - val + G[j]
			lislis = B[tmptmp:]
			if blacks in lislis:
				ans += len(B)-tmptmp-1
			else:
				ans += len(B)-tmptmp

		tmp = bisect_right(B, val)
		if len(B) == tmp:
			break

		for j in range(tmp,len(B)):
			tmptmp = bisect_right(G, B[j])
			if len(G) == tmptmp:
				break

			blacks = B[j] - val + B[j]
			lislis = G[tmptmp:]
			if blacks in lislis:
				ans += len(G)-tmptmp-1
			else:
				ans += len(G)-tmptmp


	for i,val in enumerate(B):
		tmp = bisect_right(G, val)
		if len(G) == tmp:
			break

		for j in range(tmp,len(G)):
			tmptmp = bisect_right(R, G[j])
			if len(R) == tmptmp:
				break

			blacks = G[j] - val + G[j]
			lislis = R[tmptmp:]
			if blacks in lislis:
				ans += len(R)-tmptmp-1
			else:
				ans += len(R)-tmptmp

		tmp = bisect_right(R, val)
		if len(R) == tmp:
			break

		for j in range(tmp,len(R)):
			tmptmp = bisect_right(G, R[j])
			if len(G) == tmptmp:
				break

			blacks = R[j] - val + R[j]
			lislis = G[tmptmp:]
			if blacks in lislis:
				ans += len(G)-tmptmp-1
			else:
				ans += len(G)-tmptmp

	for i,val in enumerate(G):
		tmp = bisect_right(B, val)
		if len(B) == tmp:
			break

		for j in range(tmp,len(B)):
			tmptmp = bisect_right(R, B[j])
			if len(R) == tmptmp:
				break

			blacks = B[j] - val + B[j]
			lislis = R[tmptmp:]
			if blacks in lislis:
				ans += len(R)-tmptmp-1
			else:
				ans += len(R)-tmptmp

		tmp = bisect_right(R, val)
		if len(R) == tmp:
			break

		for j in range(tmp,len(R)):
			tmptmp = bisect_right(B, R[j])
			if len(B) == tmptmp:
				break

			blacks = R[j] - val + R[j]
			lislis = B[tmptmp:]
			if blacks in lislis:
				ans += len(B)-tmptmp-1
			else:
				ans += len(B)-tmptmp

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
N = int(input())
S = input()

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

@njit
def f(S, N):
    tmp = 0
    for i in range(N):
        for j in range(i+1, N):
            k = j + (j - i)
            if k >= N:
                break
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                tmp-=1
    return tmp
                
print(f(S,N) + R*G*B)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	S = input()
	S = S[:-1]

	R = []
	G = []
	B = []
	for i,val in enumerate(S):
		if val == "R":
			R.append(i)
		elif val == "G":
			G.append(i)
		else:
			B.append(i)

	ans = 0
	for i,val in enumerate(R):
		tmp = bisect_right(G, val)
		if len(G) == tmp:
			break

		for j in range(tmp,len(G)):
			tmptmp = bisect_right(B, G[j])
			if len(B) == tmptmp:
				break

			for k in range(tmptmp,len(B)):
				if G[j] - val == B[k] - G[j]:
					pass
				else:
					ans += 1

		tmp = bisect_right(B, val)
		if len(B) == tmp:
			break

		for j in range(tmp,len(B)):
			tmptmp = bisect_right(G, B[j])
			if len(G) == tmptmp:
				break

			for k in range(tmptmp,len(G)):
				if B[j] - val == G[k] - B[j]:
					pass
				else:
					ans += 1

	for i,val in enumerate(B):
		tmp = bisect_right(G, val)
		if len(G) == tmp:
			break

		for j in range(tmp,len(G)):
			tmptmp = bisect_right(R, G[j])
			if len(R) == tmptmp:
				break

			for k in range(tmptmp,len(R)):
				if G[j] - val == R[k] - G[j]:
					pass
				else:
					ans += 1

		tmp = bisect_right(R, val)
		if len(R) == tmp:
			break

		for j in range(tmp,len(R)):
			tmptmp = bisect_right(G, R[j])
			if len(G) == tmptmp:
				break

			for k in range(tmptmp,len(G)):
				if R[j] - val == G[k] - R[j]:
					pass
				else:
					ans += 1

	for i,val in enumerate(G):
		tmp = bisect_right(B, val)
		if len(B) == tmp:
			break

		for j in range(tmp,len(B)):
			tmptmp = bisect_right(R, B[j])
			if len(R) == tmptmp:
				break

			for k in range(tmptmp,len(R)):
				if B[j] - val == R[k] - B[j]:
					pass
				else:
					ans += 1

		tmp = bisect_right(R, val)
		if len(R) == tmp:
			break

		for j in range(tmp,len(R)):
			tmptmp = bisect_right(B, R[j])
			if len(B) == tmptmp:
				break

			for k in range(tmptmp,len(B)):
				if R[j] - val == B[k] - R[j]:
					pass
				else:
					ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

n = int(input())
s = list(input())
rind = []
gind = []
bind = []

for index, val in enumerate(s):
    if val == 'R':
        rind.append(index)
    if val == 'G':
        gind.append(index)
    if val == 'B':
        bind.append(index)

# 1つめの条件を満たすものを求めてから
# 2つめの条件を満たすものを引く
ans = len(rind)*len(gind)*len(bind)
sans = 0
# R,G,B
for i in rind:
    for j in gind:
        if i < j and (j-i)+j in bind:
            sans += 1
# R,B,G
for i in rind:
    for j in bind:
        if i < j and (j-i)+j in gind:
            sans += 1
# G,B,R
for i in gind:
    for j in bind:
        if i < j and (j-i)+j in rind:
            sans += 1
# G,R,B
for i in gind:
    for j in rind:
        if i < j and (j-i)+j in bind:
            sans += 1
# B,R,G
for i in bind:
    for j in rind:
        if i < j and (j-i)+j in gind:
            sans += 1
# B,G,R
for i in bind:
    for j in gind:
        if i < j and (j-i)+j in rind:
            sans += 1

print(ans-sans)

Submission status: Time Limit Exceeded

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

Rs = []
Gs = []
Bs = []
for i, il in enumerate(S):
    if il == 'R':
        Rs.append(i)
    if il == 'G':
        Gs.append(i)
    if il == 'B':
        Bs.append(i)
num = 0
for i in Rs:
    for j in Gs:
        for k in Bs:
            if (2*i - j - k)*(2*j - k - i)*(2*k - i - j):
                num += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = input()
    r_ind = []
    g_ind = []
    b_ind = []
    # print(list(S))
    for i,s in enumerate(list(S)):
        # print(s)
        if s == "R":
            r_ind.append(i)
        if s == "G":
            g_ind.append(i)
        if s == "B":
            b_ind.append(i)
    d = len(r_ind)*len(g_ind)*len(b_ind)
    # print(d)
    temp = 0
    for i in r_ind:
        for j in g_ind:
            for k in b_ind:
                maxid = max(i,j,k)
                minid = min(i,j,k)
                if i+j+k == (maxid+minid)*3/2:
                    temp +=1
    # print(temp)
    ans = d-temp
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
s = list(input())
ans = 0
idx = [i for i in range(n)]
for i in itertools.combinations(idx, 3):
    a, b, c = i[0], i[1], i[2]
    if a < b < c:
        if s[a] == s[b] or s[a] == s[c] or s[b] == s[c]:
            continue
        elif b-a == c-b:
            continue
        else:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(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(n - 1):
    for j in range(i + 1, n):
        k = j + j - i
        if k >= n:
            continue
        if (s[i] != s[j]) & (s[i] != s[k]) & (s[j] != s[k]):
            ans -= 1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
R = []
G = []
B = []
sum = 0

N = int(input())

S = input()

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

for i in R:
   for j in G:
      for k in B:
         l = [i,j,k]
         l.sort()
         if l[1]-l[0] != l[2]-l[1]:
            sum += 1
print(sum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

R = []
B = []
G = []
p = 0
for i in S:
    if(i == "R"):
        R.append(p)
    elif(i == "B"):
        B.append(p)
    elif(i == "G"):
        G.append(p)
    p += 1
for r in R:
    for b in B:
        rb = abs(r - b)
        for g in G:
            rg = abs(r - g)
            bg = abs(b - g)
            if(rb==rg or rg==bg or bg==rb):
                continue
            else:
                sum += 1

print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
r = 0
g = 0
b = 0
R = []
G = []
B = []

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

for i in R:
    for j in G:
        if max(i,j)+abs(i-j) in B:
            ans -=1

for i in G :
    for j in B:
        if max(i,j)+abs(i-j) in R:
            ans -=1

for i in R:
    for j in B:
        if max(i,j)+abs(i-j) in G:
            ans -=1


print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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


for i in r:
    for j in g:
        for k in b:
            l = [i,j,k]
            l.sort()
            if l[1]-l[0] != l[2]-l[1]:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

Rs = []
Gs = []
Bs = []
for i, il in enumerate(S):
    if il == 'R':
        Rs.append(i)
    if il == 'G':
        Gs.append(i)
    if il == 'B':
        Bs.append(i)
num = 0
for i in Rs:
    for j in Gs:
        for k in Bs:
            ijk = sorted([i, j, k])
            if (ijk[2] - ijk[1]) != (ijk[1] - ijk[0]):
                num += 1
print(num)

Submission status: Time Limit Exceeded

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

cnt = 0

for i in range(n):
  for j in range(i+1, n):
    t = s[j:n]
    if s[i] != s[j]:
      cnt += len(t) - t.count(s[i]) - t.count(s[j])
      m = 2*j-i
      if n > m and s[m] != s[i] and s[m] != s[j]:
        cnt -= 1

      
print(cnt)

Submission status: Time Limit Exceeded

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

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

RGB = list(S)
count = 0

sub = 0

def index_Multi(List,liter):
    #Listはリスト本体・literは検索したい文字
    index_L = []
    for val in range(0,len(List)):
        if liter == List[val]:
            index_L.append(val)
    return index_L
    
r_list = index_Multi(RGB,"R")
g_list = index_Multi(RGB,"G")
b_list = index_Multi(RGB,"B")
for index, a in enumerate(RGB):
    if a == "R":
        del g_list[0:len([i for i in g_list if i < index])]
        del b_list[0:len([i for i in b_list if i < index])]
        for g in g_list:
            for b in b_list:
                if g-index == b-g or b-index == g-b:
                    sub +=1
        count = count + len(g_list)*len(b_list)
                    
    elif a == "G":
        del b_list[0:len([i for i in b_list if i < index])]
        del r_list[0:len([i for i in r_list if i < index])]
        for b in b_list:
            for r in r_list:
                if b-index == r-b or r-index == b-r:
                    sub +=1
        count = count + len(b_list)*len(r_list)
                
    elif a == "B":
        del r_list[0:len([i for i in r_list if i < index])]
        del g_list[0:len([i for i in g_list if i < index])]
        for r in r_list:
            for g in g_list:
                if r-index == g-r or g-index == r-g:
                    sub +=1
        count = count + len(g_list)*len(r_list) 
        
print(count-sub)

Submission status: Time Limit Exceeded

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

Ans = 0
for i in range(N):
  s = S[i]
  a = 0
  b = 0
  L = ["R","G","B"]
  L.remove(s)
  for j in range(i+1,N):
    t = S[j]
    if s != t:
      if t == L[0]:
        a +=1
      else:
        b +=1
  Ans += a*b

for i in range(N):
  for j in range(i+1,N):
    s = S[i]
    t = S[j]
    k = 2*j-i
    if s != t and k <= N-1:
      u = S[k]
      if t != u and u != s:
        Ans -=1
print(Ans)

Submission status: Time Limit Exceeded

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

target = set('RGB')
for i in range(N):
    #print(result)
    for j in range(i + 1, N):
        if S[i] != S[j]:
            tmp = (target - set(S[i]+S[j])).pop()
            result += S.count(tmp, j + 1, N)
            if 2*j-i < N and S[2 * j - i] == tmp:
                result -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
S = input()
#c = Counter(S)
#print (c.most_common())
#ls = list(c.values())
ans = S.count('R') * S.count('G') * S.count('B')


for i in range(N):
    for j in range(1,N):
        a = i + j
        b = i + j + j
        if (b >= N):
            pass
        else:
            l = S[i]
            m = S[a]
            r = S[b]
            if l!=m and m!=r and r!=l:
                ans -= 1
        # if (i-j<0 or i+j>=N):
        #     break
        # l = S[i-j]
        # m = S[i]
        # r = S[i+j]
        # if l!=m and m!=r and r!=l:
        #     ans -= 1
print (ans)

Submission status: Time Limit Exceeded

Solution code:

import collections


n=int(input())
s=input()
r=collections.deque()
g=collections.deque()
b=collections.deque()
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)
cnt=0
sum=len(b)*len(g)*len(r)
if len(r)*len(g)*len(b)==0:
    print(0)
else:
    for re in r:
        for gr in g:

            re1=re
            re1,gr=min(re,gr),max(re,gr)
            #print(re,gr,b)
            if (re1+gr)%2==0:
                if (re1+gr)//2 in b:
                    cnt-=1
            if 2*gr-re1 in b:
                cnt-=1
            if 2*re1-gr in b:
                cnt-=1

            #print(cnt)
    print(sum+cnt)

Submission status: Time Limit Exceeded

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

cnt = 0

for i in range(n):
  for j in range(i+1, n):
    if s[i] != s[j]:
      cnt += len(s[j:n]) - s[j:n].count(s[i]) - s[j:n].count(s[j])
      if n > 2*j-i and s[2*j-i] != s[i] and s[2*j-i] != s[j]:
        cnt -= 1

      
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def f(a, b):
    if a == 0 and b == 1: return 2
    if a == 0 and b == 2: return 1
    if a == 1 and b == 2: return 0
    if a == 1 and b == 0: return 2
    if a == 2 and b == 0: return 1
    if a == 2 and b == 1: return 0

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

t = {'R': 0, 'G': 1, 'B': 2}
tbl = [[[0, []] for j in range(3)] for i in range(n)]

sm = 0
for i in range(n):
    c = t[s[i]]
    for j in range(i):
        if s[i] != s[j]:
            c2 = t[s[j]]
            sm += tbl[j][c][0]
            if i-j in tbl[j][c][1]:
                sm -= 1
            tbl[i][f(c, c2)][0] += 1
            tbl[i][f(c, c2)][1].append(i-j)

print(sm)