[PYTHON] Lernen von ABC163C Die Grundlagen zur Verbesserung des Rechenaufwands

Einführung

Als ein Freund, der die Programmierung fast nie berührt hatte, mir sagte "Sag mir Python!" Und eine Lernsitzung abhielt, ABC163C --management Schrie: "Es ist eine gute Frage!"

Tatsächlich war ich an der Verschiebung von der Phase "Code schreiben können" zu der Phase "Rechenaufwand verbessern" in einem Problem interessiert, daher werde ich versuchen, die Interaktion zu beschreiben.

Wer ist das Ziel dieses Artikels?

Jemand, der sich bis zu einem gewissen Grad an die Grammatik von for, if, list usw. erinnert und sich der Logik sicher ist, aber irgendwie zu TLE wird.

Problemzusammenfassung

Geben Sie die Anzahl der direkten Berichte für die Mitarbeiternummern $ 1, 2, \ cdots und N $ aus. $ A_2, \ cdots, A_N $ wird angegeben, wobei der Chef des $ i $ -ten Mitarbeiters $ A_i $ ist. Die Mitarbeiternummer des Chefs ist jedoch jünger als die Mitarbeiternummer eines bestimmten Mitarbeiters.

Verlauf der Verbesserung des Berechnungsbetrags

Es war zweimal TLE und das dritte Mal AC.

1. Seien Sie zunächst ehrlich

Politik

Durchsuchen Sie den Inhalt der Bossliste A in der Reihenfolge von Mitarbeiter Nummer 1 bis N und drucken Sie die Anzahl der Treffer aus. Die Methode count () kann verwendet werden, um die angegebene Anzahl von Elementen für die Liste auszugeben. Verwenden Sie diese Methode.

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)

Einreichen!

TLE! → Warum nicht?

Dies liegt daran, dass die Einschränkung $ 2 \ le N \ le 2 \ mal 10 ^ 5 $ ist, der Berechnungsbetrag jedoch $ O (N ^ 2) \ ca. 10 ^ {10} $ beträgt.

Die Methode count () zählt die Elemente der Liste und vergleicht sie Ende-zu-Ende.

Unter der Annahme, dass die Anzahl der Elemente in der Liste N beträgt, [N-mal berechnen](Implementierung der zusätzlichen Listenanzahl) bei jedem Aufruf von "count ()". Es ist $ O (N ^ 2) $, weil es in der for-Anweisung geschrieben ist, die N-mal wiederholt wird.

Wenn im Programmierwettbewerbs-Herausforderungsbuch (allgemein als Ameisenbuch bekannt) das Zeitlimit in C ++, der Kompilierungssprache, 1 Sekunde beträgt

$ 10 ^ 6 $ Pünktlich mit einer Marge $ 10 ^ 7 $ Wahrscheinlich rechtzeitig $ 10 ^ 8 $ Streng, es sei denn, es ist ein sehr einfacher Vorgang

Es gibt. Der Rechenaufwand in Python beträgt $ 10 ^ {10} $, was zu spät ist.

2. Versuchen Sie, in der Mitte anzuhalten

Politik

Wenn die Summe der Anzahl der durch count () erhaltenen Untergebenen $ n -1 $ erreicht, besteht keine Notwendigkeit mehr, sich auf diese Methode zu verlassen. Definieren Sie daher die Variable "total", die die Summe mit dem Anfangswert 0 enthält, und addieren Sie die Ergebnisse jedes Mal, wenn Sie "count ()" aufrufen.

Da jedoch nicht bekannt ist, wie oft der überschüssige Mitarbeiter "0" ausgegeben werden soll, wird die Mitarbeiternummer zum Zeitpunkt der Kündigung in einer Variablen namens "t" gespeichert.

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)

Einreichen!

Zweiter TLE! → Ist das noch nutzlos?

Dies liegt daran, dass der ** schlechteste Berechnungsbetrag ** zu $ O (N ^ 2) $ wird. Zum Beispiel

7
1 2 3 4 5 6

In diesem Fall können Sie die for-Schleife, die count () verwendet, endgültig unterbrechen, wenn Sie die Mitarbeiternummer 1 und bis zu 6 sehen. Auf diese Weise ist unter der Annahme des schlimmsten Falls, in dem die Berechnung nicht endet, ohne die Mitarbeiter $ 1, \ cdots, N -1 $ zu betrachten, am Ende $ O (N ^ 2) $.

Es erscheint daher sehr nutzlos, jedes Mal die Anzahl der Untergebenen für jeden Mitarbeiter zu berechnen.

3. Speichern Sie die Ergebnisse in einem anderen Array

Politik

Bisher wurde die Anzahl der direkten Berichte jedes Mal für jeden Mitarbeiter berechnet, aber ich fragte mich, ob ich irgendwie eine Liste erstellen könnte, die die Anzahl der Untergebenen jedes Mitarbeiters mit $ O (N) $ enthält. Ich werde versuchen. Schließlich sollte der Inhalt der Liste einzeln ausgegeben werden.

Dazu müssen Sie nachverfolgen, wie oft Sie jede Mitarbeiternummer sehen, während Sie durch die Liste Ihrer direkten Vorgesetzten $ A $ gehen. Sie benötigen etwas, das Daten für $ N $ als Aufnahmeziel enthalten kann [^ 1], aber es ist $ N $ lang, sodass der Index jedem Mitarbeiter entspricht und das Element die Anzahl der Untergebenen ist Es sieht gut aus, es als Liste zu führen.

In der Abbildung sieht es so aus. Die obere Karte ist Liste A und der untere Container ist "Aufnahmeziel".

[^ 1]: Aufgrund der Einschränkung des Problems kann der N-te Mitarbeiter nicht der Chef sein, daher ist der Wert für den N-ten Mitarbeiter in diesem Array immer 0, berücksichtigt jedoch den Zeit- und Arbeitsaufwand bei der Ausgabe von N Personen Protokoll.

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)

• Herzlichen Glückwunsch AC![^ 2] *

[^ 2]: Da auf das Element von A nicht zugegriffen wird, ist es in Ordnung, den Status des Generators zum Zeitpunkt der Standardeingabe "A = map (int, input (). Split ()))" beizubehalten.

schließlich

Ich denke, es ist wirklich wichtig, über eine andere Politik nachzudenken, indem man schätzt, dass dieser Rechenaufwand nicht gut ist.

Ergänzung / Über die Implementierung von list.count

Auszug aus cpython / Objects über die Implementierung von 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);
}

Normalerweise schreibe ich keine C-Sprache, daher werde ich nicht rigoros darüber diskutieren.

• Sehen Sie sich die Liste Ende-zu-Ende mit einer for-Anweisung an: for (i = 0; i <Py_SIZE (self); i ++) --Überprüfen Sie die Übereinstimmung mit der if-Anweisung: if (obj == value) --Wenn sie übereinstimmen, erhöhen Sie den Zähler um 1: count ++;

Es gibt. "List.count" scheint also O (N) zu sein.