Ich habe (virtuell) an [ABC162] teilgenommen (https://atcoder.jp/contests/abc162). D Das Problem war interessant, deshalb werde ich meinen ersten Kommentarartikel schreiben!

Es war kein schöner Kommentar, aber ich habe ihn so geschrieben, dass das, was ich damals dachte, nach unten fließen würde.

Sie können das Video auf [YouTube] sehen (https://www.youtube.com/watch?v=d2Ha71q17_c).

Problem

D - RGB Triplets

Verstehen Sie die Problemstellung, während Sie Eingaben erhalten

Lesen Sie das Problem, während Sie tun, was Sie mit Hirntod tun können. Lassen Sie uns zuerst die Eingabe erhalten.

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

Sind diese beiden Bedingungen im Text?

Wie viele Möglichkeiten gibt es, R, G, B einzeln aus der Zeichenfolge $ S $ zu extrahieren?
$ I, j, k $ sollten jedoch nicht gleichmäßig verteilt sein. $ (i, j, k) = (1, 2, 3), (3, 5, 7) $ und so weiter.

Denken Sie beim Schreiben an Dummheit

Wenn Sie in Schwierigkeiten sind, seien Sie ehrlich. Denken wir nach, während wir unsere Hände bewegen.

Durchsuchen Sie alle Kombinationen mit $ i <j <k $ und fügen Sie "ans" hinzu, wenn die Bedingungen erfüllt sind.

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)

Dies ist offensichtlich $ O (N ^ 3) $. $ N <= 4000 $, also nein? Wenn Sie es auf $ O (N ^ 2) $ setzen, wird es rechtzeitig sein, aber können Sie die Anzahl der Schleifen reduzieren?

Wenn Sie sich für zwei entscheiden, wird der verbleibende automatisch entschieden

Als ich die Dreifachschleife sah, dachte ich an Otoshidama.

Kann es eine Doppelschleife sein? Wenn diese Art der Verarbeitung durchgeführt werden kann, können wir dann mit $ O (N ^ 2) $ gehen?

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]Anders als(R,G,B)Irgendein von)"

        ans += "s[j+1:n]Anzahl von c in"

        #Wie auch immer, ich,j,Die Position, in der k gleichmäßig verteilt ist, ist nicht geeignet. Reduzieren Sie sie daher um 1.
        if j+(j-i)<n and s[j+(j-i)] == c:
            ans -= 1

Kumulative Summe 3

"Die Zahl in diesem Abschnitt ist die kumulative Summe! (Übungsschwung)", also die kumulative Summe. Zu diesem Zeitpunkt müssen Sie lediglich eine kumulative Summe erstellen.

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)

Wenn Sie dies machen, kann die Anzahl der cs in s [j + 1: n] mit $ O (1) $ berechnet werden.

        # c = (s[i],s[j]Anders als(R,G,B)Irgendein von)
        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]Anzahl von 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])

Es ist irgendwie schmutzig, aber es ist ein Wettbewerb, also ist es mir egal. Das ist AC!

Ganze Quelle

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)