[GO] 4 Methoden zum Zählen der Anzahl von Ganzzahlen in einem bestimmten Intervall (einschließlich der imos-Methode) [Python-Implementierung]

Hintergrund

Als ich das ABC127 C-Problem der Wettbewerbsprogrammierung AtCoder löste, dachte ich darüber nach, wie viele gemeinsame Teile in einer Reihe aufeinanderfolgender Ganzzahlen enthalten sind. Ich fand es sehr interessant, weil es verschiedene Lösungen für das Problem gab, also beschloss ich, einen Artikel zu schreiben. Das Problem kann unter dem folgenden Link gefunden werden. Wir erklären auch das ABC127 C-Problem, seien Sie also vorsichtig mit Spoilern.

AtCoder Beginner Contest 127 C - Prison

C - Prison Beginnen wir mit der Problemstellung.

Schreiben Sie einen Überblick über die Problemstellung. Es gibt M Tore und Sie benötigen einen Ausweis, um sie zu öffnen. Es gibt N ID-Karten mit den Nummern 1 bis N. Einige Tore können nur ID-Karten mit Nummern über Li und unter Ri öffnen. Es geht darum zu zählen, wie viele ID-Karten vorhanden sind, die alle Tore öffnen können.

Betrachten wir zunächst ein Eingabebeispiel. Es gibt vier ID-Karten mit den Nummern 1, 2, 3 und 4. Es gibt 3 Tore, das 1. Tor kann mit 1, 2 und 3 ID-Karten geöffnet werden und das 2. Tor kann mit 2, 3 und 4 ID-Karten geöffnet werden. Sie können sehen, dass nur 2 und 3 ID-Karten alle Tore öffnen können. Mit anderen Worten, die Idee war, einen Produktsatz von ID-Karten zu nehmen, die alle Tore öffnen konnten.

Betrachten eines Satzes unter Verwendung der Satzrichtlinie 1

Zusammenfassend lässt sich sagen, dass diese Methode viel Rechenzeit in Anspruch nahm und zu TLE wurde und nicht bestand.

In der Regel werden die Informationen zu Minimalwert und Maximalwert der ID-Kartennummer, die ein Tor öffnen können, in einer Zeile eingegeben. Erstellen Sie daher die Nummer vom Minimalwert bis zum Maximalwert im Bereich und machen Sie sie zu einem festgelegten Typ Konvertiert zu. Die Operation wurde für alle Tore durchgeführt, und der Produktsatz wurde für alle Sätze genommen.

Betrachten Sie die Ursache von TLE. Da die maximale Anzahl von ID-Karten, die ein Tor öffnen können, $ {10 ^ {5}} $ beträgt, werden $ {10 ^ {5}} $ Daten jedes Mal in einen Satz konvertiert und M (maximal) Sie können sehen, dass dies für das Gate $ {10 ^ {5}} $) sehr rechenintensiv ist. Da die Arbeit M-mal erledigt ist, habe ich geschätzt, dass sie im schlimmsten Fall etwa $ {O (NM)} $ kosten würde. Aufgrund der Einschränkung wurde der Berechnungsbetrag zu TLE bei $ {O (10 ^ {10})} $.

Ich werde den Python-Code als Referenz setzen.

python

n, m = map(int, input().split())
line = set(range(1, n + 1))

for i in range(m):
    l, r = map(int, input().split())
    line &= set(range(l, r + 1))

print(len(line))

Überarbeitete Richtlinie 1 Richtlinie 2

Wenn ein Satz in Betracht gezogen wird, kann er in Situationen wirksam sein, in denen die ID-Karten nicht durchgehend sind, aber in diesem Fall war der Rechenaufwand groß und er war nicht wirksam. Sie können sehen, dass der Berechnungsbetrag höchstens $ {O (N)} $ betragen sollte.

Wenn Sie erneut über die Richtlinie nachdenken, sind die Daten fortlaufend. Wenn Sie also die Nummer des größten Personalausweises unter dem Mindestwert Li des Personalausweises und der kleinsten Nummer des Maximalwerts Ri speichern, ist die Anzahl zwischen ihnen dieselbe. Ich dachte es wäre die Nummer.

Ich erkannte, dass der Hintergrund dieser Richtlinie darin bestand, die Nummern auf dem Personalausweis anzuordnen, der die Tore für jedes Tor öffnet. In diesem Fall werden ID-Karten fortlaufend eingegeben, sodass diese Methode in Ordnung ist. Ri - Li + Kann mit einem Personalausweis geöffnet werden.

Wenn sich die ID-Kartenbereiche jedoch nicht überlappen, ist der Wert von Ri - Li + 1 als Einschränkung negativ. Wenn er negativ ist, gibt es keine ID-Karte, die die Bedingung erfüllt. Implementieren Sie ihn daher, um 0 auszugeben. Muss sein.

python

n, m = map(int, input().split())
l_max = 1
r_min = 10 ** 5

for i in range(m):
    l, r = map(int, input().split())
    l_max = max(l, l_max)
    r_min = min(r, r_min)

print(max(0, r_min - l_max + 1))

Ich konnte mit diesem Code eine Klimaanlage bekommen. Ich bin damit zufrieden, wenn ich nur AC nehme, aber als ich mir die Kommentarsendung ansah, gab es einen Kommentar, der besagte, dass sie durch die imos-Methode gelöst wurde, also wurde ich interessiert und überlegte eine andere Lösung.

Richtlinie 3 vor Eingabe der imos-Methode

Bevor ich an der imos-Methode arbeite, möchte ich eine Methode betrachten, die der imos-Methode ähnlich ist. Abschließend denke ich, dass diese Methode viel Berechnung erfordert und zu TLE führt. Unsere imos-Methode löst dieses Problem.

Lassen Sie uns unsere Gedanken organisieren. In Anbetracht der Anzahl der Tore, die ID-Karten öffnen können, beträgt die Anzahl der ID-Karten, die alle Tore öffnen können, M, da jedes Tor geöffnet werden kann. Wenn es kleiner als M ist, können einige Tore nicht geöffnet werden. Mit anderen Worten, Sie können die Anzahl der ID-Karten zählen, die M Tore öffnen können.

Dann möchte ich es umsetzen. Bereiten Sie zunächst ein Array vor, um zu speichern, wie viele Tore die ID-Kartennummer öffnen kann. Ich habe ein Array namens cardid_2_num_map vorbereitet. Die Anzahl der Elemente ist eins mehr als der Maximalwert des Personalausweises. Die eingegebene Zahl ist 1 oder mehr und N oder weniger, daher habe ich versucht, den Fehler zu reduzieren, indem ich ihn so verwende, wie er bei der Angabe des Index ist. Das 0. Array wird niemals verwendet.

Wenn Sie ein Array betrachten, dessen Karten-ID-Nummer ein Index von 0 bis $ {10 ^ 5} $ ist und dessen Inhalt die Anzahl der Tore enthält, die die ID-Karte öffnen kann, [0, 1, 2, 2, 1 , 0, ...] ist das Array, das Sie im Fall des Eingabebeispiels erhalten möchten.

In Anbetracht dessen, dass für dupliziert wird, scheint der Rechenaufwand groß zu sein. Die maximale Reihenfolge der Berechnungsmenge beträgt $ {O (NM)} $ und ist TLE wie bei Betrachtung des Produktsatzes. Die imos-Methode löst dieses Problem. Wir werden es im nächsten Abschnitt diskutieren.

python

n, m = map(int, input().split())
cardid_2_num_map = [0] * (10**5 + 1)

for i in range(m):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        cardid_2_num_map[j] += 1

max_sum_num = max(cardid_2_num_map)
count_max_card = cardid_2_num_map.count(max_sum_num)

if max_sum_num == m:
    print(count_max_card)
else:
    print(0)

Imos-Methode, diesmal die führende Rolle, Politik 4

Ich werde den Artikel veröffentlichen, den ich als Referenz verwendet habe.

Imos Labor-Imos Labor Die imos-Methode ist ein Algorithmus, mit dem es gelungen ist, den Rechenaufwand zu reduzieren, indem die kumulative Summe verwendet wurde, um die Anzahl der Vorkommen aufeinanderfolgender Zahlen zu zählen und die Verarbeitung zu erfassen, die jedes Mal zu einer gezählt wurde.

Kehren wir zum obigen Problem zurück und denken darüber nach. Ich zählte die Anzahl der ID-Karten, die das Tor öffnen konnten, und aktualisierte die Werte im Array. Die maximale Reihenfolge des Berechnungsbetrags ist $ {O (NM)} $, was TLE ist. Es scheint, dass es gelöst werden kann, wenn die Reihenfolge auf ungefähr $ {O (M)} $ unterdrückt werden kann.

Wenn Sie also zum Eingabebeispiel zurückkehren, gibt es vier ID-Karten, die mit 1, 2, 3 bzw. 4 nummeriert sind. Es gibt 3 Tore, das 1. Tor kann mit 1, 2 und 3 ID-Karten geöffnet werden und das 2. Tor kann mit 2, 3 und 4 ID-Karten geöffnet werden.

Ähnlich wie in Richtlinie 3 lautet die Karten-ID-Nummer im Index 0, 1, 2, 3, 4, ..., $ {10 ^ 5} $, und der Inhalt des Arrays ist die Nummer, mit der die ID-Karte das Tor öffnen kann. Wenn Sie das beibehaltene Array betrachten, ist die Sequenz [0, 1, 2, 2, 1, 0, ...] die Sequenz, die Sie im Fall des Eingabebeispiels erhalten möchten. Der 0. Index wird nicht verwendet, da die Karten-ID 0 anzeigt. Die imos-Methode wird verwendet, um ein solches Array zu erhalten.

Initialisieren Sie zunächst das Array mit $ {10 ^ 5 + 2} $ Elementen und einem Wert von 0. Die Absicht von +2 wird später erklärt. Das erste Tor kann mit 1, 2 und 3 Karten geöffnet werden, sodass die Indexnummer 1 +1 und die Indexnummer 4 -1 ist. [0, 1, 0, 0, -1, 0, ..., 0] In ähnlicher Weise kann das zweite Tor mit 2, 3 und 4 ID-Karten geöffnet werden, sodass die Indexnummer 2 +1 und die Indexnummer 5 -1 ist. [0, 1, 1, 0, -1, -1, ..., 0] Da -1 für den Index +1 am rechten Ende des Personalausweises verwendet wird, wird die Anzahl der Elemente im Array um 1 zu $ {10 ^ 5} $ und +2 addiert (+1 wurde durchgeführt, um der Indexnummer und der Eingabe zu entsprechen. ).

Als nächstes wird die kumulative Summe dieses Arrays vom Index 0 bis zum Ende genommen. A[i + 1] = A[i] + A[i + 1] halten. Infolgedessen kann die gewünschte Sequenz [0, 1, 2, 2, 1, 0, ...] wie in Richtlinie 3 erhalten werden.

Wenn dann der Maximalwert des Arrays gleich der Anzahl der Gates ist, gibt es ID-Karten, die alle Gates öffnen können, und die Anzahl der ID-Karten mit dem Maximalwert wird gezählt. Die maximale Reihenfolge des Berechnungsbetrags betrug ungefähr $ {O (M)} $, und ich konnte AC.

python

n, m = map(int, input().split())
cardid_2_num_map = [0] * (10**5 + 2)

for i in range(m):
    l, r = map(int, input().split())
    cardid_2_num_map[l] += 1
    cardid_2_num_map[r + 1] -= 1

for i in range(1, n + 1):
    cardid_2_num_map[i] += cardid_2_num_map[i - 1]

max_sum_num = max(cardid_2_num_map)
count_max_card = cardid_2_num_map.count(max_sum_num)

if max_sum_num == m:
    print(count_max_card)
else:
    print(0)

Erwägung

Durch Hinzufügen von +1 zum Index am linken Ende des Bereichs, den Sie zählen möchten, und -1 zum Index am rechten Ende von +1 ist es möglich, +1 nur vom linken zum rechten Ende zu addieren, wenn die kumulative Summe endgültig genommen wird, und für alle Bereiche. Sie können die Anzahl der Auftritte gleichzeitig zählen.

x <Tun Sie nichts ganz links Linkes Ende <= x <= Bereich des rechten Endes wird um +1 erhöht Da der Bereich des rechten Endes <x nichts tut

Wir sind in der Lage, die beabsichtigte Zählung durchzuführen.

Diese Denkweise kann auf mehrere Dimensionen angewendet werden und der Rechenaufwand kann reduziert werden, daher fand ich sie sehr interessant. Die Abbildungen in dem Artikel, auf den ich mich bezog, waren sehr leicht zu verstehen. Das ist alles.