I participated (virtually) in ABC162. D Problem was interesting, so I will write the first commentary article!

It wasn't a beautiful commentary, but I wrote it so that what I thought at that time would flow down.

You can see the video on YouTube.

problem

Understand the problem statement while receiving input

Read the problem while doing what you can do with brain death. Let's receive the input first.

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

Are these two conditions in the text?

How many ways to extract R, G, B one by one from the string $ S $?
However, $ i, j, k $ should not be evenly spaced. $ (i, j, k) = (1, 2, 3), (3, 5, 7) $ and so on.

Consider while writing stupidity

If you are in trouble, be honest. Think while moving your hands.

Search all combinations where $ i <j <k $, and add ʻans` if the conditions are met.

ans = 0

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

print(ans)

This is obviously $ O (N ^ 3) $. $ N <= 4000 $, so no? If you set it to $ O (N ^ 2) $, it will be in time, but can you reduce the number of loops?

If you decide two, the remaining one will be decided automatically

When I saw the triple loop, I thought of Otoshidama.

Can it be a double loop? If this kind of processing can be done, can we go with $ O (N ^ 2) $?

for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        c = "(s[i],s[j]Different from(R,G,B)Any of)"

        ans += "s[j+1:n]Number of c in"

        #However, i,j,The position where k is evenly spaced is not suitable, so reduce it by 1.
        if j+(j-i)<n and s[j+(j-i)] == c:
            ans -= 1

Cumulative sum 3

"The number in the interval is the cumulative sum! (Practice swing)", so it will be the cumulative sum. At this point, all you have to do is make a cumulative sum.

ruisekiR = [0] * (n+1)
ruisekiG = [0] * (n+1)
ruisekiB = [0] * (n+1)

for i,c in enumerate(s):
    ruisekiR[i+1] = ruisekiR[i] + ( 1 if c == "R" else 0)
    ruisekiG[i+1] = ruisekiG[i] + ( 1 if c == "G" else 0)
    ruisekiB[i+1] = ruisekiB[i] + ( 1 if c == "B" else 0)

If you make this, the number of cs in s [j + 1: n] can be found by $ O (1) $.

        # c = (s[i],s[j]Different from(R,G,B)Any of)
        c = "R"
        if "R" in (s[i], s[j]):
            c = "G"
            if "G" in (s[i], s[j]):
                c = "B"

        # ans += (s[j+1:n]Number of c in)
        if c == "R":
            ans += (ruisekiR[n] - ruisekiR[j])
        if c == "G":
            ans += (ruisekiG[n] - ruisekiG[j])
        if c == "B":
            ans += (ruisekiB[n] - ruisekiB[j])

It's kind of dirty, but it's a contest so I don't care. This is AC!

Whole source

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

ruisekiR = [0] * (n+1)
ruisekiG = [0] * (n+1)
ruisekiB = [0] * (n+1)

for i,c in enumerate(s):
    ruisekiR[i+1] = ruisekiR[i] + ( 1 if c == "R" else 0)
    ruisekiG[i+1] = ruisekiG[i] + ( 1 if c == "G" else 0)
    ruisekiB[i+1] = ruisekiB[i] + ( 1 if c == "B" else 0)

ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        c = "R"
        if "R" in (s[i], s[j]):
            c = "G"
            if "G" in (s[i], s[j]):
                c = "B"

        if c == "R":
            ans += (ruisekiR[n] - ruisekiR[j])
        if c == "G":
            ans += (ruisekiG[n] - ruisekiG[j])
        if c == "B":
            ans += (ruisekiB[n] - ruisekiB[j])

        if j+(j-i)<n and s[j+(j-i)] == c:
            ans -= 1

print(ans)