Si vous parcourez la discussion jusqu'à présent, vous remarquerez qu'il existe une méthode de jugement. En fait, le remarquer est la clé de ce problème, donc si vous n'êtes pas venu au but, pensez-y pendant un moment.

………C'est vrai! Lorsque la sous-chaîne $ T $ est réorganisée, les $ "A" $ et $ "T" $ contenus dans ** $ T $ doivent être présents pour avoir une chaîne complémentaire de $ T $. Doit être égal en nombre et $ "C" $ et $ "G" $ doivent être égaux en nombre **.

Maintenant le problème est ** "$ S $ est une sous-chaîne contiguë non vide $ T $, et $ T $ contient des nombres égaux de " A " et " T " , Et trouvez le nombre de choses qui ont le même nombre de $ "C" $ et $ "G" $ "**.

De cette manière, il est également important pour les professionnels de la concurrence de «remplacer les phrases problématiques par des formes faciles à comprendre».

Étape 2: Pensez à une solution simple

Maintenant que le problème a été résumé brièvement, considérons une solution. À ce stade, la contrainte de la valeur donnée par l'entrée standard est très utile. Dans ce cas, $ N <= 5000 $, donc la solution $ O (N ^ 2) $ sera à temps (si vous ne comprenez pas le concept d'ordre de calcul, [ce site](https: // bmf-tech) .com / posts / O (ordre) notation et comment calculer le montant du calcul de l'algorithme #: ~: text = Le montant du calcul (ordre) est un indice exprimé sous forme de ratio.)).

Maintenant que nous connaissons la limite supérieure du montant du calcul, réfléchissons sérieusement à la solution. L'étape 1 montre que si vous connaissez le nombre de $ "A", "T", "C", "G" $ dans $ T $, vous pouvez déterminer si $ T $ a une chaîne complémentaire. Donc, pour le moment, je vais l'écrire honnêtement.

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)

Si vous mettez réellement dans un cas de test, vous pouvez voir que vous cherchez la bonne réponse. Cependant, le montant de calcul de ce programme est de $ O (N ^ 3) $, ce qui vous bloquera dans le délai d'exécution (Lorsque vous le soumettez, cela ressemble à ceci / contests / arc104 / soumissions / 17643029)). De cette façon, si vous estimez d'abord la limite supérieure du montant du calcul, vous pouvez vous empêcher d'encourir une pénalité en soumettant un code qui devient TLE.

Étape 3: Accélérez le programme

À partir de là, réfléchissons à la façon d'accélérer. En premier lieu, il en coûte $ O (N ^ 2) $ pour spécifier une sous-chaîne, donc ** "Détermine si une chaîne complémentaire existe avec $ O (1) $" Vous devez penser à ** ou ** "comment résoudre sans spécifier de sous-chaînes individuelles" **. ~~ Ce problème semble bien fonctionner si vous pensez au premier. Ne vous inquiétez pas si vous ne le savez pas maintenant, car vous comprendrez progressivement «sur quels points il faut se concentrer pour accélérer» au fur et à mesure que vous gérez le montant. ~~

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
//Prétraitement pour utiliser la somme cumulée
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)
}
//À partir de maintenant, c'est la même chose que la méthode simple que j'ai créée plus tôt
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)

Plus précisément, je voudrais expliquer comment résoudre ce dernier cas. Voyons d'abord comment fonctionne le programme écrit à l'étape 2. Ensuite, vous remarquerez que le calcul est inutile. Plus précisément, c'est la partie ↓.

for j in i+1..<n{
    //Abréviation
    for k in i...j{
        //Abréviation
    }

Si vous suivez le déroulement du programme en se déplaçant soigneusement un par un,

Trouvez la valeur de $ i ... j $ dans une boucle Trouvez la valeur de $ → i ... j + 1 $ dans une boucle Trouvez la valeur de $ → i ... j + 2 $ dans une boucle Répétez ci-dessous $ → $

Vous pouvez voir que cela fonctionne comme ça. Cependant, si vous y réfléchissez bien, la valeur de $ i ... j + 1 $ peut être obtenue en ajoutant simplement la valeur de $ j + 1 $ à la valeur de $ i ... j $. Recalculer la valeur de $ i ... j $ est un calcul inutile. De même, lorsque vous trouvez la valeur de $ i ... j + 2 $, ajoutez simplement la valeur de $ j + 2 $ à la valeur de $ i ... j + 1 $.

Donc ce que je veux dire, c'est que ** une valeur une fois calculée peut être utilisée pour trouver la valeur suivante **. Si cela est amélioré, le montant du calcul peut être réduit à $ O (N ^ 2) $ sans utiliser la somme cumulée. Une fois mis en œuvre, ce sera comme suit.

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)

Si vous essayez d'extraire la partie qui a été utilisée pour des calculs inutiles de cette manière, ce sera une histoire qui dit "C'est vrai", mais c'est difficile à remarquer sauf si vous y êtes habitué. Au début, il est recommandé de le résoudre avec le sentiment de "penser à une solution simple" → "en regardant le déroulement du programme et en recherchant des calculs inutiles".

finalement

C'est la fin de l'explication. Il a peut-être été difficile de comprendre l'explication (je suis désolé, je ne suis pas assez fort), mais j'espère que cela traduit l'atmosphère générale lors de la résolution du problème. Comme je l'ai écrit au début, si vous avez des questions, n'hésitez pas à commenter ou Twitter.