Wenn Sie die Diskussion bisher durchgehen, werden Sie feststellen, dass es eine Methode zur Beurteilung gibt. In der Tat ist es der Schlüssel zu diesem Problem, es zu bemerken. Wenn Sie also nicht auf den Punkt gekommen sind, denken Sie eine Weile darüber nach.

………Korrekt! Wenn die Teilzeichenfolge $ T $ neu angeordnet wird, müssen die in ** $ T $ enthaltenen $ "A" $ und $ "T" $ vorhanden sein, damit eine Zeichenfolge zu $ T $ komplementär ist. Muss in der Anzahl gleich sein und $ "C" $ und $ "G" $ müssen in der Anzahl gleich sein **.

Jetzt ist das Problem ** "$ S $ ist ein zusammenhängender nicht leerer Teilstring $ T $, und die Anzahl von " A " und " T " in $ T $ ist gleich. , Und finden Sie die Anzahl der Dinge, die die gleiche Anzahl von $ "C" $ und $ "G" $ "** haben.

Auf diese Weise ist es für Wettkampfprofis auch wichtig, "Problemsätze durch leicht verständliche Formen zu ersetzen".

Schritt 2: Überlegen Sie sich eine einfache Lösung

Nachdem das Problem kurz zusammengefasst wurde, betrachten wir eine Lösung. Zu diesem Zeitpunkt ist die Einschränkung des durch die Standardeingabe angegebenen Werts sehr hilfreich. In diesem Fall ist $ N <= 5000 $, sodass die $ O (N ^ 2) $ -Lösung rechtzeitig ist (wenn Sie das Konzept der Berechnungsreihenfolge nicht verstehen, [diese Site](https: // bmf-tech) .com / posts / O (Auftrag) -Notation und Berechnung des Berechnungsbetrags des Algorithmus #: ~: text = Der Berechnungsbetrag (Auftrag) ist ein Index, der als Verhältnis ausgedrückt wird.)).

Nachdem wir die Obergrenze des Berechnungsbetrags kennen, sollten wir uns ernsthaft mit der Lösung befassen. Schritt 1 zeigt, dass Sie bestimmen können, ob $ T $ eine komplementäre Zeichenfolge hat, wenn Sie die Anzahl von $ "A", "T", "C", "G" $ in $ T $ kennen. Also werde ich es vorerst ehrlich schreiben.

let input = readLine()!.split(separator: " ")
let n = Int(input[0])!
let s = Array(input[1]).map{String($0)}
var answer = 0
for i in 0..<n-1{
    for j in i+1..<n{
        var ac = 0
        var tc = 0
        var cc = 0
        var gc = 0
        for k in i...j{
            if s[k] == "A"{ac += 1}
            if s[k] == "T"{tc += 1}
            if s[k] == "C"{cc += 1}
            if s[k] == "G"{gc += 1} 
        }
        if ac == tc && cc == gc{answer += 1}
    }
}
print(answer)

Wenn Sie tatsächlich einen Testfall einreichen, können Sie sehen, dass Sie nach der richtigen Antwort suchen. Der Rechenaufwand für dieses Programm beträgt jedoch $ O (N ^ 3) $, was dazu führt, dass Sie im Ausführungszeitlimit stecken bleiben (Wenn Sie es tatsächlich einreichen, sieht es so aus / contests / arc104 / submissions / 17643029)). Auf diese Weise können Sie, wenn Sie zuerst die Obergrenze des Berechnungsbetrags schätzen, verhindern, dass Sie eine Strafe erhalten, indem Sie einen Code senden, der zu TLE wird.

Schritt 3: Beschleunigen Sie das Programm

Lassen Sie uns von hier aus überlegen, wie Sie beschleunigen können. Erstens kostet es $ O (N ^ 2) $, einen Teilstring anzugeben, also ** "Bestimmen Sie, ob mit $ O (1) $ eine komplementäre Zeichenfolge existiert." Sie müssen sich ** oder ** überlegen, wie Sie ohne Angabe einzelner Teilzeichenfolgen lösen können **. ~~ Dieses Problem scheint gut zu funktionieren, wenn Sie an das erstere denken. Machen Sie sich keine Sorgen, wenn Sie es jetzt nicht wissen, denn Sie werden nach und nach verstehen, "auf welche Punkte Sie sich konzentrieren sollten, um schneller zu werden", wenn Sie den Betrag verwalten. ~~

let input = readLine()!.split(separator: " ")
let n = Int(input[0])!
let s = input[1]
var aa:[Int] = [0]
var tt:[Int] = [0]
var cc:[Int] = [0]
var gg:[Int] = [0]
var a = 0
var t = 0
var c = 0
var g = 0
//Vorverarbeitung zur Verwendung der kumulierten Summe
for i in s{
    if i == "A"{a += 1}
    if i == "T"{t += 1}
    if i == "C"{c += 1}
    if i == "G"{g += 1}
    aa.append(a)
    tt.append(t)
    cc.append(c)
    gg.append(g)
}
//Von hier an ist es dasselbe wie die einfache Methode, die ich zuvor erstellt habe
var ans = 0
for i in 0...n-1{
    for j in i+1...n{
        if aa[j]-aa[i] == tt[j]-tt[i] && cc[j]-cc[i] == gg[j]-gg[i]{
            ans += 1
        }
    }
}
print(ans)

Insbesondere möchte ich erklären, wie der letztere Fall gelöst werden kann. Lassen Sie uns zunächst sehen, wie das in Schritt 2 geschriebene Programm funktioniert. Dann werden Sie feststellen, dass die Berechnung verschwenderisch ist. Insbesondere ist es der ↓ Teil.

for j in i+1..<n{
    //Abkürzung
    for k in i...j{
        //Abkürzung
    }

Wenn Sie dem Programmablauf folgen und sich vorsichtig nacheinander bewegen,

Finden Sie den Wert von $ i ... j $ in einer Schleife Finden Sie den Wert von $ → i ... j + 1 $ in einer Schleife Finden Sie den Wert von $ → i ... j + 2 $ in einer Schleife Wiederholen Sie unter $ → $

Sie können sehen, dass es so funktioniert. Wenn Sie jedoch darüber nachdenken, können Sie den Wert von $ i ... j + 1 $ erhalten, indem Sie einfach den Wert von $ j + 1 $ zum Wert von $ i ... j $ addieren. Es ist eine verschwenderische Berechnung, den Wert von $ i ... j $ neu zu berechnen. Wenn Sie den Wert von $ i ... j + 2 $ ermitteln, addieren Sie einfach den Wert von $ j + 2 $ zum Wert von $ i ... j + 1 $.

Ich meine also, dass ** ein einmal berechneter Wert verwendet werden kann, um den nächsten Wert zu finden **. Wenn dies verbessert wird, kann der Berechnungsbetrag ohne Verwendung der kumulierten Summe auf $ O (N ^ 2) $ reduziert werden. Wenn implementiert, wird es wie folgt sein.

let input = readLine()!.split(separator: " ")
let n = Int(input[0])!
let s = Array(input[1]).map{String($0)}
var answer = 0
for i in 0..<n-1{
    var ac = 0
    var tc = 0
    var cc = 0
    var gc = 0
    for j in i..<n{
        if s[j] == "A"{ac += 1}
        if s[j] == "T"{tc += 1}
        if s[j] == "C"{cc += 1}
        if s[j] == "G"{gc += 1} 
        if ac == tc && cc == gc{answer += 1}
    }
}
print(answer)

Wenn Sie versuchen, den Teil, der für unnötige Berechnungen verwendet wurde, auf diese Weise zu extrahieren, wird eine Geschichte mit der Aufschrift "Das stimmt" angezeigt, die jedoch nur schwer zu bemerken ist, wenn Sie daran gewöhnt sind. Zu Beginn wird empfohlen, das Problem mit dem Gefühl zu lösen, "über eine einfache Lösung nachzudenken" → "den Programmfluss zu betrachten und nach unnötigen Berechnungen zu suchen".

Schließlich

Dies ist das Ende der Erklärung. Die Erklärung mag an vielen Stellen schwer zu verstehen gewesen sein (ich bin nicht stark genug, es tut mir leid), aber ich hoffe, sie vermittelt die allgemeine Atmosphäre bei der Lösung des Problems. Wie ich zu Beginn schrieb, können Sie bei Fragen gerne einen Kommentar abgeben oder Twitter.