Apprendre de ABC163C Les bases de l'amélioration de la quantité de calcul

introduction

Quand un ami qui n'avait presque jamais touché à la programmation m'a dit «Dis-moi Python!» Et a tenu une session d'étude, ABC163C --management Criait: "C'est une bonne question!"

En fait, j'étais intéressé par le passage de la phase «être capable d'écrire du code» à la phase «être capable d'améliorer la quantité de calcul» dans un problème, donc je vais essayer de décrire l'interaction.

Qui est la cible de cet article

Quelqu'un qui se souvient dans une certaine mesure de la grammaire de for, if, list, etc. et qui a confiance en la logique mais devient en quelque sorte TLE.

Résumé du problème

Affiche le nombre de subordonnés directs pour les employés de 1, 2, \ cdots et N $. $ A_2, \ cdots, A_N $ est donné, où le patron du $ i $ e employé est $ A_i $. Cependant, le numéro d'employé du patron est plus jeune que le numéro d'employé d'un certain employé.

Trajectoire de l'amélioration du montant de calcul

C'était TLE deux fois et AC la troisième fois.

1. Tout d'abord, soyez honnête

politique

Recherchez le contenu de la liste de boss A dans l'ordre de l'employé numéro 1 à N et imprimez le nombre de résultats. La méthode count () peut être utilisée pour afficher le nombre spécifié d'éléments pour la liste, alors utilisez-la.

abc163_c.py

N = int(input())
A = list(map(int, input().split()))

for i in range(1, N + 1):
    count = A.count(i)
    print(count)

Soumettre!

TLE! → Pourquoi pas?

En effet, la contrainte est $ 2 \ le N \ le 2 \ times 10 ^ 5 $, mais le montant du calcul est $ O (N ^ 2) \ approx 10 ^ {10} $.

La méthode count () compte les éléments de la liste, en les comparant de bout en bout.

En supposant que le nombre d'éléments dans la liste est N, [calculer N fois](# Implémentation du nombre de listes supplémentaires) chaque fois que count () est appelé. C'est $ O (N ^ 2) $ car il est écrit dans l'instruction for qui boucle N fois.

De plus, dans le livre de défi du concours de programmation (communément appelé livre de fourmi), si le délai est de 1 seconde en C ++ qui est le langage de compilation

10 $ ^ 6 $ Dans le temps avec une marge 10 $ ^ 7 $ Probablement à temps 10 $ ^ 8 $ Strict sauf s'il s'agit d'un processus très simple

Il y a. Le montant du calcul en Python est de 10 $ ^ {10} $, ce qui est trop tard.

2. Essayez de vous arrêter au milieu

politique

Lorsque la somme du nombre de subordonnés obtenu par count () atteint $ n -1 $, il n'est plus nécessaire de s'appuyer sur cette méthode. Par conséquent, définissez la variable «total» qui contient la somme avec une valeur initiale de 0, et ajoutez les résultats à chaque fois que vous appelez «count ()».

Cependant, comme on ne sait pas combien de fois l'employé excédentaire «0» doit être sorti, le numéro d'employé au moment de la cessation d'emploi est enregistré dans une variable appelée «t».

abc163_c.py

N = int(input())
A = list(map(int, input().split()))

total = 0
t = 0
for i in range(1, N):
    count = A.count(i)
    print(count)
    total += count
    if total == N - 1:
        t = i
        break
for _ in range(t, N):
    print(0)

Soumettre!

Deuxième TLE! → Est-ce toujours inutile?

En effet, le ** pire montant de calcul ** devient $ O (N ^ 2) $. Par exemple

7
1 2 3 4 5 6

Dans ce cas, vous pouvez enfin rompre la boucle for qui utilise count () lorsque vous voyez l'employé numéro 1 et jusqu'à 6. De cette façon, en supposant le pire des cas où le calcul ne se termine pas sans regarder les employés $ 1, \ cdots, N -1 $, c'est $ O (N ^ 2) $ à la fin.

Il semble donc inutile de calculer à chaque fois le nombre de subordonnés pour chaque employé.

3. Enregistrez les résultats dans un autre tableau

politique

Jusqu'à présent, le nombre de subordonnés directs était calculé pour chaque employé à chaque fois, mais je me demandais si je pourrais en quelque sorte faire une liste contenant le nombre de subordonnés de chaque employé avec $ O (N) $. Je vais essayer. Enfin, le contenu de la liste doit être affiché un par un.

Pour ce faire, vous devez suivre le nombre de fois où vous voyez chaque numéro d'employé en parcourant la liste de vos supérieurs directs $ A $. Vous avez besoin de quelque chose qui peut contenir des données pour $ N $ comme destination d'enregistrement [^ 1], mais il a une longueur de $ N $ pour que l'index corresponde à chaque employé et que l'élément soit le nombre de subordonnés. Il semble bon de le garder sous forme de liste.

Sur la figure, cela ressemble à ceci. La carte supérieure est la liste A et le conteneur inférieur est "Destination d'enregistrement".

[^ 1]: En raison de la limitation du problème, le Nième employé ne peut pas être le patron, donc la valeur du Nième employé dans ce tableau est toujours 0, mais compte tenu du temps et des efforts lors de la sortie, N personnes Minutes.

abc163_c.py

N = int(input())
A = list(map(int, input().split()))

B = [0] * N
for i in A:
    B[i - 1] += 1
for i in B:
    print(i)

• Félicitations AC![^ 2] *

[^ 2]: Puisque l'élément de A n'est pas accédé, il est OK même si ʻA = map (int, input (). Split ())) `le garde dans l'état de générateur au moment de l'entrée standard.

à la fin

Je pense qu'il est vraiment important de réfléchir à différentes politiques en estimant que ce montant de calcul n'est pas bon.

Supplément / À propos de l'implémentation de list.count

Extrait de cpython / Objects ce qu'est l'implémentation de list.count.

listobject.c

/*[clinic input]
list.count

     value: object
     /

Return number of occurrences of value.
[clinic start generated code]*/

static PyObject *
list_count(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=b1f5d284205ae714 input=3bdc3a5e6f749565]*/
{
    Py_ssize_t count = 0;
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        PyObject *obj = self->ob_item[i];
        if (obj == value) {
           count++;
           continue;
        }
        Py_INCREF(obj);
        int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
        Py_DECREF(obj);
        if (cmp > 0)
            count++;
        else if (cmp < 0)
            return NULL;
    }
    return PyLong_FromSsize_t(count);
}

Je n'écris généralement pas en langage C, donc je n'en discuterai pas rigoureusement

• Regardez la liste de bout en bout avec une instruction for: for (i = 0; i <Py_SIZE (self); i ++) --Vérifiez la correspondance avec l'instruction if: ʻif (obj == value) --S'ils correspondent, avancez le compteur de 1:count ++;`

Il y a. Donc list.count semble être O (N).