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:
mod = 10**9 + 7
mod2 = 2**61 + 1
int1 = lambda x: int(x) - 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools


# input = sys.stdin.readline
def input():
    return sys.stdin.readline().strip("\n").strip(" ")


_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12
INF = 9223372036854775807  # 符号つきlong longの最大値。10の18乗より大きく、10の19乗より小さい

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    N = iip()
    A = iip()

    B = []
    for i in A:
        if i == "R":
            B.append(0)
        elif i == "G":
            B.append(1)
        elif i == "B":
            B.append(2)

    #print(B)

    C = []
    n = [0, 0, 0]
    for i in B:
        n[i] += 1
        C.append([i for i in n])

    #print(C)

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

            cur = sum(C[-1]) - C[-1][B[i]] - C[-1][B[j]] # 先にある数字を全部足す
            cur -= sum(C[j]) - C[j][B[i]] - C[j][B[j]]

            idx = j + (j-i)
            if idx < N and B[idx] != B[i] and B[idx] != B[j]:
                cur -= 1
            ans += cur

            #print(cur)

    print(ans)


#####################################################ライブラリ集ここから


def kiriage_warizan(a, b):
    return -(-a // b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def iipt(l, listed=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0]  # 間違って要素１個のタプルを渡されても受け取る
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()


def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N - 1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x:x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x:x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):  # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2**N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret


def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n**0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  # modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_)**2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido=1):  # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r - l > seido:
        # print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r = x
            else:
                l = x


        elif func(x) > target:
            r = x
        else:
            # print(r, l)
            l = x

    # print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r - l > 1:
        x = (l + r) // 2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                # for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
from collections import Counter

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
S = sys.stdin.buffer.readline().decode().rstrip()

eq = 0
nb = 0
l, m, r = 0, 1, 2
for w in range(1, N):
    l = 0
    m = l + w
    r = m + w
    while r < N:
        eq += S[l] == S[m] or S[m] == S[r] or S[r] == S[l]
        nb += 1
        l += 1
        m += 1
        r += 1
rgb = Counter(S)
na = 0
na += (N - rgb['R']) * (rgb['R'] * (rgb['R'] - 1) // 2)
na += (N - rgb['G']) * (rgb['G'] * (rgb['G'] - 1) // 2)
na += (N - rgb['B']) * (rgb['B'] * (rgb['B'] - 1) // 2)
na += (rgb['R'] - 1) * (rgb['R'] - 2) * rgb['R'] // 6
na += (rgb['B'] - 1) * (rgb['B'] - 2) * rgb['B'] // 6
na += (rgb['G'] - 1) * (rgb['G'] - 2) * rgb['G'] // 6

total = N * (N - 1) * (N - 2) // 6
print(total - na - nb + eq)

# ans = 0
# na2 = 0
# for l, m, r in itertools.combinations(range(N), r=3):
#     if abs(r - m) != abs(m - l):
#         ans += S[l] != S[m] and S[m] != S[r] and S[r] != S[l]
#     na2 += S[l] == S[m] or S[m] == S[r] or S[r] == S[l]
# print(ans)
# print(na2, na)

Submission status: Accepted

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

dicts = {'R':0, 'G':0, 'B':0}
for i in s:
    dicts[i] += 1

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

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

print(ans)

Submission status: Accepted

Solution code:

table = { "R": 0, "G": 1, "B": 2 }

N = int(input())
S = [table[c] for c in input().strip()]

counts = [0, 0, 0]

for c in S:
	counts[c] += 1

count_diff = counts[0] * counts[1] * counts[2]

count_diff_si = 0
for i in range(0, N - 2):
	ci = S[i]
	for j in range(i + 1, N - 1):
		k = j + j - i
		if k >= N:
			break
		cj = S[j]
		ck = S[k]
		if ci != cj and ci != ck and cj != ck:
			count_diff_si += 1
print(count_diff - count_diff_si)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    S = list(input())
    d = []
    c = [0,0,0]
    R = 0
    G = 0
    B = 0
    for i in range(N-1,-1,-1):
        if S[i] == 'R':
            R += 1
        if S[i] == 'G':
            G += 1
        if S[i] == 'B':
            B += 1
        d.append([R,G,B])
            
    d.reverse()
    ans = 0
    for i in range(N):
        if S[i] == 'R':
            ans += d[i][1] * d[i][2]
        if S[i] == 'G':
            ans += d[i][0] * d[i][2]
        if S[i] == 'B':
            ans += d[i][0] * d[i][1]
        for k in range(N):
            if i + 2 * k >= N:
                break
            if S[i] == 'R':
                if S[i + k] == 'G' and S[i + 2 * k] == 'B':
                    ans -= 1
                if S[i + k] == 'B' and S[i + 2 * k] == 'G':
                    ans -= 1 
            if S[i] == 'G':
                if S[i + k] == 'R' and S[i + 2 * k] == 'B':
                    ans -= 1
                if S[i + k] == 'B' and S[i + 2 * k] == 'R':
                    ans -= 1 
            if S[i] == 'B':
                if S[i + k] == 'R' and S[i + 2 * k] == 'G':
                    ans -= 1
                if S[i + k] == 'G' and S[i + 2 * k] == 'R':
                    ans -= 1 

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
color = [[0 for _ in range(3)] for _ in range(N+1)]
for i, c in enumerate(S):
    for j in range(3):
        color[i+1][j] = color[i][j]
    if c == "R":
        color[i+1][0] += 1
    elif c == "G":
        color[i+1][1] += 1
    elif c == "B":
        color[i+1][2] += 1

rn = color[N][0]
gn = color[N][1]
bn = color[N][2]

ans = 0
for i, c in enumerate(S):
    if i == 0 or i == N-1:
        continue
    j = 1
    while i-j >=0 and i+j <=N-1:
        if S[i-j] != S[i] and S[i] != S[i+j] and S[i-j] != S[i+j]:
            ans -= 1
        j += 1
    if c == "R":
        ans += color[i][1] * (bn - color[i+1][2])
        ans += color[i][2] * (gn - color[i+1][1])
    elif c == "G":
        ans += color[i][0] * (bn - color[i+1][2])
        ans += color[i][2] * (rn - color[i+1][0])
    elif c == "B":
        ans += color[i][0] * (gn - color[i+1][1])
        ans += color[i][1] * (rn - color[i+1][0])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
R=[0]*n
G=[0]*n
B=[0]*n
rcnt=0;gcnt=0;bcnt=0
ans=0
for i in range(n):
    if s[i]=="R":R[i]=R[i-1]+1;B[i]=B[i-1];G[i]=G[i-1];rcnt+=1
    elif s[i]=="G":G[i]=G[i-1]+1;R[i]=R[i-1];B[i]=B[i-1];gcnt+=1
    else:B[i]=B[i-1]+1;R[i]=R[i-1];G[i]=G[i-1];bcnt+=1
for i in range(n-1):
    for j in range(i+1,n):
        if s[i]==s[j]:continue
        if "R"!=s[i] and "R"!=s[j]:
            if 2*j-i>=n:
                ans+=rcnt-R[j]
            else:
                ans+=rcnt-R[j]
                if s[2*j-i]=="R":ans-=1
        elif "B"!=s[i] and "B"!=s[j]:
            if 2*j-i>=n:
                ans+=bcnt-B[j]
            else:
                ans+=bcnt-B[j]
                if s[2*j-i]=="B":ans-=1
        else:
            if 2*j-i>=n:
                ans+=gcnt-G[j]
            else:
                ans+=gcnt-G[j]
                if s[2*j-i]=="G":ans-=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    S = input()
    
    acc = [[0] * 3 for _ in range(N + 1)]
    for i in range(1, N + 1):
        acc[i] = acc[i - 1][:]
        if S[i - 1] == 'R':
            acc[i][0] += 1
        elif S[i - 1] == 'G':
            acc[i][1] += 1
        else:
            acc[i][2] += 1
    
    ans = 0
    for i, j in combinations(range(N - 1), 2):
        si, sj = S[i], S[j]
        if si == sj:
            continue
        if 'R' not in [si, sj]:
            ans += acc[N][0] - acc[j][0]
            t = j + j - i
            if t < N:
                ans -= S[t] == 'R'
        elif 'G' not in [si, sj]:
            ans += acc[N][1] - acc[j][1]
            t = j + j - i
            if t < N:
                ans -= S[t] == 'G'
        else:
            ans += acc[N][2] - acc[j][2]
            t = j + j - i
            if t < N:
                ans -= S[t] == 'B'
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	S = list(input())
	LR = [0] * (N + 1)
	LG = [0] * (N + 1)
	LB = [0] * (N + 1)
	for i in range(N):
		LR[i + 1] = LR[i]
		LG[i + 1] = LG[i]
		LB[i + 1] = LB[i]
		if S[i] == "R":
			LR[i + 1] += 1
		elif S[i] == "G":
			LG[i + 1] += 1
		else:
			LB[i + 1] += 1

	# print(LR)
	# print(LG)
	# print(LB)
	ans = 0
	for i in range(N):
		if S[i] == "R":
			ans += LG[i] * (LB[N] - LB[i + 1]) + LB[i] * (LG[N] - LG[i + 1])
		elif S[i] == "G":
			ans += LR[i] * (LB[N] - LB[i + 1]) + LB[i] * (LR[N] - LR[i + 1])
		else:
			ans += LR[i] * (LG[N] - LG[i + 1]) + LG[i] * (LR[N] - LR[i + 1])

	#引く作業
	for i in range(N):
		for j in range(1, N + 1):
			if i + 2 * j > N - 1:
				break
			if S[i] != S[i + j] and S[i + j] != S[i + 2 * j] and S[i] != S[i + 2 * j]:
				ans -= 1

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#MLE注意！

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    s = input().rstrip()
    res = s.count('R') * s.count('G') * s.count('B')

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

    print(res - cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

CR = [0]*N
CG = [0]*N
CB = [0]*N

for i in range(N):
    if S[i] == "R":
        CR[i]+=1
    elif S[i] == "G":
        CG[i]+=1
    else:
        CB[i]+=1

rR = [0]*N
rG = [0]*N
rB = [0]*N

for i in range(N-1):
    I = N-i-2
    rR[I] = rR[I+1]+CR[I+1]
    rG[I] = rG[I+1]+CG[I+1]
    rB[I] = rB[I+1]+CB[I+1]
    
ans = 0
for i in range(N):
    I = i
    a = S[I]
    for j in range(N-i-1):
        J = i+j+1
        b = S[J]
        if a != b:
            add = 0
            if "R" != a and "R" != b:
                add += rR[J]
                d = J-I
                if J+d < N:
                    add -= CR[J+d] 
                
            elif "G" != a and "G" != b:
                add += rG[J]
                d = J-I
                if J+d < N:
                    add -= CG[J+d] 
            else:
                add += rB[J]
                d = J-I
                if J+d < N:
                    add -= CB[J+d] 
            ans+=add
            #print(a,b,add)
            
print(ans)
#print(rR,rG,rB)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
yo = input()
if(yo[-1]=='\n'):
	yo=yo[:-1]
n=int(yo)
s=input()
if(s[-1]=='\n'):
	s=s[:-1]
preb=[0 for i in range(n)]
preg=[0 for i in range(n)]
prer=[0 for i in range(n)]
b=0; g=0; r=0
for i in range(n-1,-1,-1):
	if(s[i]=='R'):
		r+=1
	elif(s[i]=='G'):
		g+=1
	else:
		b+=1
	preb[i]=b; prer[i]=r; preg[i]=g
# print(preb)
# print(preg)
# print(prer)
l=[prer,preg,preb]
s=s.replace('R','0')
s=s.replace('G','1')
s=s.replace('B','2')
ans=0
# print(s)
for i in range(n):
	for j in range(i+1,n):
		if(s[i]!=s[j]):
			if(j+1>=n):
				continue
			ct = l[(3-int(s[i])-int(s[j]))][j+1]
			diff = j-i
			if((j+diff)<n and s[j+diff]==str(3-int(s[i])-int(s[j]))):
				ct-=1
			ans+=ct
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input().rstrip()
    ans = 0
    a = [[0]*3 for _ in range(n)]
    rgb = [None]*n
    for i in range(n):
        if s[i] == "R":
            rgb[i] = 0
        elif s[i] == "G":
            rgb[i] = 1
        else:
            rgb[i] = 2
    a[n-1][rgb[n-1]] += 1
    for i in reversed(range(n-1)):
        a[i][rgb[i]] += 1
        for j in range(3):
            a[i][j] += a[i+1][j]
    for i in range(n-2):
        for j in range(i+1, n-1):
            if rgb[i] == rgb[j]:
                continue
            x = 3 - rgb[i] - rgb[j]
            L = j + (j - i)
            ans += a[j+1][x]
            if L < n and rgb[L] == x:
                ans -= 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

N = int(readline())
S = readline().rstrip()

R, G, B = 'R', 'G', 'B'

nr, ng, nb = (S.count(v) for v in (R, G, B))

ans = nr * ng * nb

for w in range(1, N // 2 + 1):
    for i in range(N):
        if i + 2*w >= N:
            break
        if S[i] != S[i + w] and S[i + w] != S[i + 2*w] and S[i + 2*w] != S[i]:
            ans -= 1

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    s = input()
    rR = [0] * (n + 1)
    rG = [0] * (n + 1)
    rB = [0] * (n + 1)
    
    for i in range(n - 1,-1,-1):
        if s[i] == 'R':
            rR[i] = rR[i + 1] + 1
            rG[i] = rG[i + 1]
            rB[i] = rB[i + 1]
        elif s[i] == 'B':
            rR[i] = rR[i + 1] 
            rG[i] = rG[i + 1]
            rB[i] = rB[i + 1] + 1
        else:
            rR[i] = rR[i + 1] 
            rG[i] = rG[i + 1] + 1
            rB[i] = rB[i + 1]
    
    ans = 0
    for i in range(1,n - 1):
        if s[i] == 'R':
            for j in range(i):
                if s[j] == 'B':
                    if 2 * i - j < n and s[2 * i - j] == 'G':
                        ans += rG[i + 1] - 1
                    else:
                        ans += rG[i + 1]
                elif s[j] == 'G':
                    if 2 * i - j < n and s[2 * i - j] == 'B':
                        ans += rB[i + 1] - 1
                    else:
                        ans += rB[i + 1] 
        elif s[i] == 'B':
            for j in range(i):
                if s[j] == 'R':
                    if 2 * i - j < n and s[2 * i - j] == 'G':
                        ans += rG[i + 1] - 1
                    else:
                        ans += rG[i + 1]
                elif s[j] == 'G':
                    if 2 * i - j < n and s[2 * i - j] == 'R':
                        ans += rR[i + 1] - 1
                    else:
                        ans += rR[i + 1] 
        
        elif s[i] == 'G':
            for j in range(i):
                if s[j] == 'R':
                    if 2 * i - j < n and s[2 * i - j] == 'B':
                        ans += rB[i + 1] - 1
                    else:
                        ans += rB[i + 1]
                elif s[j] == 'B':
                    if 2 * i - j < n and s[2 * i - j] == 'R':
                        ans += rR[i + 1] - 1
                    else:
                        ans += rR[i + 1] 
                        
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

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

d = {"R":[],"G":[],"B":[]}

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

res = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i]==s[j]:
            continue
        if s[i]=="R":
            if s[j]=="G":
                k = "B"
            else:
                k = "G"
        elif s[i]=="G":
            if s[j]=="R":
                k = "B"
            else:
                k = "R"
        else:
            if s[j]=="G":
                k = "R"
            else:
                k = "G"
        
        x = lower_bound(d[k],j)
        if x<0 or x>=len(d[k]):
            continue
        ki = j + (j-i)
        res += len(d[k])-x
        if ki<n and s[ki]==k:
            if s[ki]==k:
                res -= 1
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
S = input()
c = Counter(S)
ans = c['R']*c['G']*c['B']
for i in range(N):
  for j in range(i+1,N):
    k = j-i+j
    if k>N-1:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[i]!= S[k]:
      ans -= 1
print(ans)

Submission status: Accepted

Solution code:

from sys import stdin
import sys
# sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]


def main():
	n=int(nextLine())
	s=nextLine()

# 	n=4000
# 	import numpy as np
# 	rr=np.random.randint(0,3,n)
# 	s=[]
# 	for r in rr:
# 		if r==0: s.append("R")
# 		if r==1: s.append("G")
# 		if r==2: s.append("B")
# 	s="".join(s)
# 	print(s)
	
# 	index=([],[],[])
# 	for i,si in enumerate(s):
# 		if si=="R": index[0].append(i)
# 		elif si=="G": index[1].append(i)
# 		elif si=="B": index[2].append(i)
# 	print(index)
		
	nums=[0,0,0]
	for i,si in enumerate(s):
		if si=="R": nums[0]+=1
		elif si=="G": nums[1]+=1
		elif si=="B": nums[2]+=1
# 	print(nums)
	
	ss=nums[0]*nums[1]*nums[2]
	for skip in range(n):
		length=skip*2+3
		if length>n: break
		for i0 in range(n-length+1):
			i1=i0+skip+1
			i2=i1+skip+1
			if s[i0]!=s[i1] and s[i1]!=s[i2] and s[i2]!=s[i0]:
				ss-=1
	print(ss)
			
	
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    s = input()
    r = s.count("R")
    g = s.count("G")
    b = s.count("B")
    ans = r * g * b
    for diff in range(1, 1 + (n - 1) // 2):
        for first in range(n - diff * 2):
            i = s[first]
            j = s[first + diff]
            k = s[first + diff * 2]
            if i != j and j != k and k != i:
                ans -= 1
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N=int(input())
S=input()
M=[0 if s=='R' else 1 if s=='G' else 2 for s in S]

C = [[0] * (N+1) for _ in range(3)]
for i in range(N-1,-1,-1):
    for j in range(3):
        C[j][i] = C[j][i+1]+1 if M[i]==j else C[j][i+1]

ans=0
for i in range(N):
    for j in range(i+1,N):
        if M[i]==M[j]: continue
        k=3-M[i]-M[j]
        ans+=C[k][j+1]
        if j+(j-i) < N and M[j+(j-i)]==k: ans-=1
print(ans)

Submission status: Accepted

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

def jdg(i,j):
    mm = j+(j-i)
    # print(i,j,mm)
    if mm<N:
        if S[mm]==S[i] or S[mm]==S[j]:
            return True  
        else:
            return False
    else:
        return True

mm1 = S.count("R")
mm2 = S.count("G")
mm3 = S.count("B")

ans = mm1*mm2*mm3

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

print(ans)

Submission status: Accepted

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

a = s.count('R')
b = s.count('G')
c = s.count('B')

ans = a * b * c

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input().strip().lower())
r = 0
g = 0
b = 0
extra = 0
for i in range(n):
    if s[i] == 'r':
        r += 1
    elif s[i] == 'g':
        g += 1
    elif s[i] == 'b':
        b += 1

    for j in range(1, min(i + 1, n - i)):
        left = s[i - j]
        mid = s[i]
        right = s[i + j]
        if left != mid and left != right and mid != right:
            extra += 1

print(r*g*b-extra)

Submission status: Accepted

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

for i in range(N):
    if S[i] == 'R':
        r += 1
        ans += g * b
        for j in range(i-1,-1,-1):
            if 2*j-i >= 0 and set([S[j],S[2*j-i]]) == set(['G','B']):
                ans -= 1
    elif S[i] == 'G':
        g += 1
        ans += b * r
        for j in range(i-1,-1,-1):
            if 2*j-i >= 0 and set([S[j],S[2*j-i]]) == set(['B','R']):
                ans -= 1
    else:
        b += 1
        ans += r * g
        for j in range(i-1,-1,-1):
            if 2*j-i >= 0 and set([S[j],S[2*j-i]]) == set(['R','G']):
                ans -= 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
color = {"R":0, "G":0, "B":0}
for i in range(n):
    color[s[i]] += 1
temp = color["R"] * color["G"] * color["B"]
count = 0
for i in range((n - 1) // 2):
    for j in range(n - (i + 1) * 2):
        if s[j] != s[j + i + 1] and s[j] != s[j + i * 2 + 2] and s[j + i + 1] != s[j + i * 2 + 2]:
            count += 1
print(temp - count)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
  return list(map(int,input().split()))
def m(): #複数文字
  return map(int,input().split())
def onem(): #Nとかの取得
  return int(input())
def s(x): #圧縮
  a = []
  if len(x) == 0:
    return []
  aa = x[0]
  su = 1
  for i in range(len(x)-1):
    if aa != x[i+1]:
      a.append([aa,su])
      aa = x[i+1]
      su = 1
    else:
      su += 1
  a.append([aa,su])
  return a
def jo(x): #listをスペースごとに分ける
  return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
  return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = onem()

s = input()[:-1]

R = [0 for _ in range(n)]
B = [0 for _ in range(n)]
G = [0 for _ in range(n)]

co = 0

if s[0] == "R":
  R[0] = 1
elif s[0] == "G":
  G[0] = 1
else:
  B[0] = 1

for i in range(1,n):
  if s[i] == "R":
    R[i] += 1
  elif s[i] == "G":
    G[i] += 1
  else:
    B[i] += 1
  R[i] += R[i-1]
  G[i] += G[i-1]
  B[i] += B[i-1]

for i in range(1,n-1):
  if s[i] == "G":
    for j in range(i):
      if s[j] == "R":
        un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "B" else 0)
        co += B[-1] - B[i] - un
      elif s[j] == "B":
        un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "R" else 0)
        co += R[-1] - R[i] - un

  elif s[i] == "R":
    for j in range(i):
      if s[j] == "G":
        un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "B" else 0)
        co += B[-1] - B[i] - un
      elif s[j] == "B":
        un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "G" else 0)
        co += G[-1] - G[i] - un

  elif s[i] == "B":
    for j in range(i):
      if s[j] == "G":
          un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "R" else 0)
          co += R[-1] - R[i] - un
      elif s[j] == "R":
          un = (1 if (i + (i-j) < n) and s[i + (i - j)] == "G" else 0)
          co += G[-1] - G[i] - un
    
print(co)

Submission status: Accepted

Solution code:
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)
b=set(b)
lb=len(b)
ans=0
for i in r:
    for j in g:
        x,y=min(i,j),max(i,j)
        ans_=lb
        if x-(y-x) in b:
            ans_-=1
        if y+(y-x) in b:
            ans_-=1
        if (x%2==y%2) and (y-x)//2+x in b:
            ans_-=1
        ans+=ans_
print(ans)