J'ai participé (virtuellement) à ABC162. D Le problème était intéressant, je vais donc écrire mon premier article de commentaire!

Ce n'était pas un beau commentaire, mais je l'ai écrit pour que ce que je pensais à ce moment-là s'écoule.

Vous pouvez voir la vidéo sur YouTube.

problème

D - RGB Triplets

Comprendre l'énoncé du problème lors de la réception des entrées

Lisez le problème tout en faisant ce que vous pouvez faire avec la mort cérébrale. Commençons par recevoir les commentaires.

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

Ces deux conditions figurent-elles dans le texte?

Combien de façons d'extraire R, G, B une par une de la chaîne $ S $?
Cependant, $ i, j, k $ ne doivent pas être régulièrement espacés. $ (i, j, k) = (1, 2, 3), (3, 5, 7) $ et ainsi de suite.

Considérez en écrivant la folie

Si vous êtes en difficulté, soyez honnête. Réfléchissons en bougeant nos mains.

Recherchez dans toutes les combinaisons $ i <j <k $ et ajoutez ʻans` si les conditions sont remplies.

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)

C'est évidemment $ O (N ^ 3) $. $ N <= 4000 $, donc non? Si vous le définissez sur $ O (N ^ 2) $, ce sera dans le temps, mais pouvez-vous réduire le nombre de boucles?

Si vous en décidez deux, le reste sera décidé automatiquement

Quand j'ai vu la triple boucle, j'ai pensé à Otoshidama.

Cela peut-il être une double boucle? Si ce type de traitement peut être fait, pouvons-nous utiliser $ 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]Différent de(R,G,B)N'importe quel)"

        ans += "s[j+1:n]Nombre de c dans"

        #Cependant, je,j,La position où k est régulièrement espacé ne convient pas, réduisez-la donc de 1.
        if j+(j-i)<n and s[j+(j-i)] == c:
            ans -= 1

Somme cumulée 3

"Le nombre dans la section est la somme cumulée! (Swing d'entraînement)", donc ce sera la somme cumulée. À ce stade, tout ce que vous avez à faire est de faire une somme cumulative.

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)

Si vous faites cela, le nombre de cs dans s [j + 1: n] peut être calculé par $ O (1) $.

        # c = (s[i],s[j]Différent de(R,G,B)N'importe quel)
        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]Nombre de c dans)
        if c == "R":
            ans += (ruisekiR[n] - ruisekiR[j])
        if c == "G":
            ans += (ruisekiG[n] - ruisekiG[j])
        if c == "B":
            ans += (ruisekiB[n] - ruisekiB[j])

C'est un peu sale, mais c'est un concours donc je m'en fiche. C'est AC!

Toute la 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)