Ich werde erklären, wie das ** C-Problem "Viele Anforderungen" ** des ** AtCoder Beginners Contest 165 ** mit ** Python 3 ** so sorgfältig wie möglich gelöst werden kann.
Es war so lange, dass ich nur das C-Problem aufteilte.
Ich werde auf drei Arten erklären.
--Verwenden Sie itertools.combinations_with_replacement () (am einfachsten)
ABC165C『Many Requirements』
** Schwierigkeit **: ★★★★★★★★★★★ (Schwierige D-Problemstufe!) ** Typ **: Round-Robin-Idee, Suche mit Tiefenpriorität (andere Methoden sind ebenfalls verfügbar), vergangene Übungen
Zunächst ist es schwierig, die Problemstellung zu lesen und die Bedeutung zu verstehen. Selbst wenn Sie die Bedeutung verstehen, müssen Sie daran denken, alle Sequenzen zu erstellen und zu überprüfen. Und selbst wenn Sie wissen, dass Sie ein Round-Robin machen werden, können Sie es nicht lösen, ohne zu wissen, wie man eine Zahlenfolge macht.
Um ehrlich zu sein, ist es die Schwierigkeit des schwierigen D-Problems.
Als ich es geschafft habe, die Problemstellung zu entschlüsseln, scheint es, dass ich eine Folge von $ N $ Länge machen möchte. Die Länge $ N $ beträgt 2-10. Wenn die Zahlenspalte die Bedingungen erfüllt, erhalten Sie eine Punktzahl. Ich möchte, dass Sie den Maximalwert dieser Punktzahl angeben.
Die Zahlen in der Zahlenspalte sind größer oder gleich $ 1 $ und kleiner oder gleich $ M $. Die Obergrenze von $ M $ liegt bei 1-10. Und die Nummer muss mit der vorherigen Nummer identisch oder größer sein. Dies bedeutet, dass die Anzahl in der Mitte nicht abnehmen sollte.
Angenommen, $ N = 4 $ und $ M = 3 $.
Lassen Sie mich ein Beispiel für die Anzahl der zulässigen Spalten geben.
Lassen Sie mich Ihnen ein Beispiel für eine schlechte Zahlenfolge geben. $ 1,1,3,2 $ ($ 2 $ ist größer als $ 3 $, Sie können also nicht nach 3 kommen) $ 1,2,3,4 $ ($ 4 $ überschreitet die Obergrenze $ M = 3 $) $ 0,1,2,3 $ ($ 0 $ ist nicht gut, weil es über $ 1 $ liegt) $ 1,1,1 $ (Länge $ N = 4 $) $ 1,1,1,1,1 $ (wie oben)
Schließlich gibt es $ Q $ Bedingungen. Es gibt maximal 50 Bedingungen, und eine Bedingung besteht aus vier ganzen Zahlen $ a, b, c, d $.
Die Bedingung ist
($ b $ th in der erstellten Sequenz) - ($ a $ th in der erstellten Sequenz) = $ c $
Ist zu sein. In diesem Fall erhalten Sie eine Punktzahl von $ d $.
Zum Beispiel ist die Bedingung
Zum Beispiel geben $ 1,1,2,3 $ und $ 1,2,3,3 $ Ihnen $ 5 $ Punkte, aber $ 1,2,2,2 $ und $ 2,2,3,3 Ich bekomme kein $.
Ich möchte, dass Sie den Maximalwert der Gesamtpunktzahl ermitteln, indem Sie dies für alle Bedingungen überprüfen.
Das einzige Problem bei diesem Problem besteht darin, alle möglichen Sequenzen zu erstellen und jede Punktzahl zu berechnen, um den Maximalwert zu ermitteln. Daher können Sie es nie lösen, wenn Sie nicht erkennen, dass Sie alles treffen können.
Die maximale Länge der Zahlenfolge beträgt 10, und die maximale Länge beträgt 10, daher glaube ich nicht, dass viele Zahlen erstellt werden können. Wenn Sie nach der genauen Nummer fragen, die in der PDF-Erklärung angegeben ist, lautet diese ~~ 20C10 = 184756 ~~ $ \ _ {19} C_ {10} = 92378 $. (Korrigiert am 03.05. Danke @forzaMilan!)
Und da die Bedingung für das Erhalten von Punkten maximal 50 ist, scheint es, dass es rechtzeitig ist, selbst wenn Sie alle Zahlen überprüfen, die Sie gemacht haben.
Nun, selbst wenn Sie erkennen, dass Sie ein Round-Robin erstellen können, können Sie es nur lösen, wenn Sie wissen, wie Sie alle Sequenzen erstellen.
Das Problem beim Erstellen solcher Zahlen und Zeichenfolgen tritt manchmal auf, sodass Sie es möglicherweise verstehen, wenn Sie ähnliche Probleme lösen. Wenn Sie es jedoch nicht wissen, wird es schwierig sein, es während des Wettbewerbs zu finden.
Es gibt verschiedene Möglichkeiten, eine Folge von Zahlen zu erstellen.
--Verwenden Sie itertools.combinations_with_replacement (am einfachsten)
Am einfachsten ist es, die Funktion "Kombinationen_mit_Ersetzung ()" des Moduls "itertools" zu verwenden. Wie ich später erfahren habe, können Sie mit dieser Funktion einfach alle Sequenzen in diesem Problem auflisten.
Der Name ist lang und schwer zu merken, aber eine nützliche Funktion. Um es zu verwenden, müssen Sie das Modul "itertools" importieren.
modules_with_replacement () ist eine Funktion, die "doppelte Kombinationen" auflistet. Der Unterschied zu den üblichen "Kombinationen" "Kombinationen ()" besteht darin, dass Sie dasselbe Element mehrmals auswählen können.
Es gibt zwei Eingaben: ein "iterierbares" Element und die Häufigkeit, mit der das Element abgerufen wird (Spaltenlänge). "Iterable" ist auf Englisch "iterable" und bedeutet "wiederholt". Diejenigen, die nach dem In der for-Schleife verwendet werden können, z. B. "list", "taple", "range ()" und "zeichenfolge".
Die Ausgabe sind alle "überlappenden Kombinationen", die unter den Eingabebedingungen vorgenommen werden können. Jede Ausgabe erfolgt in "Reihenfolge der Eingabeelemente". Das ist wichtig.
Mal sehen, was mit der for-Schleife und print () erstellt wird. Nehmen wir an, es gibt drei Elemente, "Bereich (1,4)", dh "(1,2,3)", und die Länge beträgt 2.
#Weil es lang ist, Kamm_Importieren Sie mit dem Namen rplc
from itertools import combinations_with_replacement as comb_rplc
for seq in comb_rplc(range(1, 4), 2):
print(seq)
(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 3)
(3, 3)
Es umfasst auch solche, in denen dasselbe Element mehrmals vorkommt, z. B. (1, 1) und (2, 2). Da die Eingabe in der Größenordnung von 1,2,3 liegt, gibt es keine nächste Zahl, die kleiner als die vorherige Zahl ist, wie (2, 1) und (3, 2).
Vergleichen Sie mit der üblichen Kombination "Kombinationen ()".
from itertools import combinations
for seq in combinations(range(1, 4), 2):
print(seq)
(1, 2)
(1, 3)
(2, 3)
Natürlich gibt es keine (1, 1) oder (2, 2), die dasselbe Element zweimal auswählen.
Versuchen Sie, den Eingang auf "CBA" zu setzen. Wie für wird es als drei Elemente betrachtet: "C", "B" und "A".
for seq in comb_rplc("CBA", 2):
print(seq)
('C', 'C')
('C', 'B')
('C', 'A')
('B', 'B')
('B', 'A')
('A', 'A')
Da ich in der Reihenfolge C, B, A eingebe, ist die Ausgabe auch in dieser Reihenfolge angeordnet. Bitte beachten Sie, dass sie nicht in der Reihenfolge von ABC erscheinen.
Die Bedingung für die in diesem Problem erstellte Nummernfolge ist, dass die nächste Nummer nicht kleiner als die vorherige Nummer ist. Wenn die Eingabe in aufsteigender Reihenfolge erfolgt, erfolgt die Ausgabe ebenfalls in aufsteigender Reihenfolge, sodass diese Bedingung ohne Erlaubnis erfüllt wird.
Da die Länge der Sequenz $ N $ ist und die Obergrenze der Zahl $ M $ ist, kann "Kombinationen mit Ersetzung (Bereich (1, m + 1), n)" alle möglichen Sequenzen auflisten.
Importieren Sie mit einer Abkürzung wie "aus itertools importieren Sie Kombinationen mit Ersetzung als comb_rplc", um Unordnung in Ihrem Code zu vermeiden.
from itertools import combinations_with_replacement as comb_rplc
n, m, q = list(map(int, input().split()))
#req ist[[a1,b1,c1,d1],[a2,b2,c2,d2]……]Es ist eine Liste der Liste, die enthält
req = [list(map(int, input().split())) for _ in range(q)]
ans = 0
#seq ist ein Taple der Länge n
for seq in comb_rplc(range(1, m + 1), n):
score = 0
for a, b, c, d in req:
#Das k-te der in der Problemstellung geschriebenen Zahlenspalte ist k, wenn es sich um einen Index handelt-Beachten Sie, dass es 1 sein wird
if seq[b - 1] - seq[a - 1] == c:
score += d
ans = max(ans, score)
print(ans)
"mit Ersatz" bedeutet "ersetzen". "Ersetzen" bedeutet häufiger "Ersetzen" oder "Ersetzen", aber das ist nicht der Fall.
Angenommen, Sie haben einen nummerierten Ball in Ihrer Tasche. In einer normalen "Kombination", dh "ohne Ersatz", wird die entfernte Kugel nicht in den Beutel zurückgeführt. Notieren Sie sich in der "Duplikatkombination" "mit Ersatz" die Anzahl der herausgenommenen Bälle und legen Sie sie wieder in den Beutel.
Es kann einfacher sein, sich an diese Funktion zu erinnern, wenn Sie die Bedeutung auf diese Weise verstehen.
Ich konnte für dieses Problem eine Folge von Zahlen mit kombinationen_mit_replacement () erstellen, aber da die Bedingungen komplexer werden, muss ich sie selbst implementieren.
Wenn Sie alle Zeichenfolgen und Zahlenzeichenfolgen erstellen möchten, die eine bestimmte Bedingung erfüllen, gibt es eine äußerst vielseitige Methode namens "Warteschlange rekursiv".
Wie der Name schon sagt, wird eine Datenstruktur (Array) verwendet, die als Warteschlange bezeichnet wird. Wie eine Warteschlange aussieht, ist ein Array, das "herausnimmt, was Sie zuerst eingegeben haben" (FIFO: First In, First OUT). Es ist eine wichtige, die beim Studium von Algorithmen herauskommt.
Es wird eine Zeichenfolge verwendet, die noch aus der Warteschlange erstellt wird, ein Zeichen hinzugefügt und wiederholt zur Warteschlange hinzugefügt.
Dann werden schließlich alle Zahlen generiert, die Sie erstellen möchten.
Um Warteschlangen in Python zu verwenden, müssen Sie das deque () des sammlungen Moduls importieren.
"deque" ist eine Abkürzung für "Double-Ended-Queue" und ein Datentyp namens "Both Ends Queue". Die Aussprache ist "Deck".
Die Deque kann Elemente entweder vom Anfang oder vom Ende extrahieren und hinzufügen. Das heißt, es ist aufwärtskompatibel mit Stapeln und Warteschlangen.
Es gibt zwei Methoden zum Hinzufügen und Abrufen von Elementen zum Deque.
append (): Fügen Sie rechts ein Element hinzu (Ende)
appendleft (): Füge links (zuerst) ein Element hinzu
pop () Extrahiere das rechte (End-) Element
popleft (): Extrahiert das linke (erste) Element
"Nehmen Sie heraus, was Sie zuerst eingegeben haben" in der Warteschlange wird umschrieben als "wenn Sie es von rechts eingeben" und "wenn Sie es von links herausnehmen".
Mit anderen Worten, wenn Sie "append ()" zum Einfügen und "popleft ()" zum Extrahieren verwenden, können Sie die Warteschlange selbst realisieren.
Im Fall eines Stapels "Nehmen Sie heraus, was Sie später eingegeben haben". Wenn Sie ihn also mit "append ()" herausnehmen, ist es "pop ()".
Werfen wir einen Blick auf den Pseudocode-Stil der Warteschlangenwiederholung und sehen, was er bewirkt.
from collections import deque
que = deque()
que.append(Ausgangszustand) # Ausgangszustandを入れないと、while queを素通りします
while que:
Aktuellen Zustand= que.popleft() #Von Anfang an herausnehmen
#Etwas tun
die if-Bedingung erfüllen:
#Etwas tun
else:
Nächster Zustand=Aktuellen Zustand+ α #In einigen Fällen werden für for mehrere "nächste Zustände" erstellt.
que.append(Nächster Zustand) #Zum Ende hinzufügen
while que bedeutet, dass wenn que nicht leer ist, es als True beurteilt wird, und wenn es leer ist, wird es als False beurteilt, sodass eine Schleife ausgeführt wird, bis der Inhalt von que leer ist.
Wenn die Bedingungen erfüllt sind, tritt eine Endlosschleife auf, wenn keine Aktion ausgeführt wird, ohne die Warteschlange zu erweitern.
Dadurch kann die Warteschlange neu gestartet werden.
from collections import deque
#Eine Funktion, die die Punktzahl einer Folge von Zahlen berechnet
def calc(seq):
score = 0
for a, b, c, d in req:
if seq[b - 1] - seq[a - 1] == c:
score += d
return score
n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]
ans = 0
que = deque()
#Zuerst in der Zahlenspalte,[1]～[m]Wird zur Warteschlange hinzugefügt,
#Eigentlich steht dieses Problem am Anfang der Sequenz[1]Es kann gelöst werden, indem nur der Fall von betrachtet wird.
for i in range(1, m + 1):
que.append([i])
while que:
seq = que.popleft()
if len(seq) == n:
#Berechnen Sie nun, da die Länge n ist, die Punktzahl
score = calc(seq)
ans = max(ans, score)
else:
#Die nächste hinzuzufügende Zahl ist, dass die Untergrenze die letzte Zahl in der aktuellen Sequenz ist und die Obergrenze m ist.
for i in range(seq[-1], m + 1):
seq_next = seq + [i]
que.append(seq_next)
print(ans)
Ich werde schreiben, wie sich der Inhalt der Warteschlange ändert, wenn "m = 3" und "n = 3".
[1], [2], 3 [2],[3],[1,1],[1,2],[1,3] [3],[1,1],[1,2],[1,3],[2,2],[2,3] [1,1],[1,2],[1,3],[2,2],[2,3],[3,3] [1,2],[1,3],[2,2],[2,3],[3,3],[1,1,1],[1,1,2],[1,1,3] [1,3],[2,2],[2,3],[3,3],[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3] …… (weggelassen) [2,3,3],[3,3,3] [3,3,3] Keine (Ende)
Sie nehmen die ganz links heraus und fügen eine Nummer hinzu und fügen sie rechts hinzu. Auf diese Weise können Sie alle Spalten erstellen.
Eine Länge von 3 bedeutet, dass die Sequenz vollständig ist. Sie berechnen also nur die Punktzahl und fügen der Warteschlange keinen neuen Status hinzu. Infolgedessen ist die Warteschlange möglicherweise leer und Sie geraten nicht in eine Endlosschleife.
Dieses Problem kann auch mit einem Stapel "Von rechts einlegen und von rechts herausnehmen" anstelle der Warteschlange "Von rechts einlegen und von links herausnehmen" gelöst werden.
Übrigens kann der Stapel eine reguläre Liste anstelle einer Deque sein. Dies liegt daran, dass die Methoden "append ()" und "pop ()" auch in normalen Listen enthalten sind.
Grundsätzlich wird jedoch empfohlen, "deque ()" als Warteschlange zu behandeln und zu lösen. Es gibt drei Vorteile.
--Deque arbeitet schneller, wenn die Anzahl der Elemente zunimmt ――Wenn Sie Warteschlangen verwenden, ist es manchmal nützlich, dass Zahlen und Zeichenfolgen in "lexikalischer Reihenfolge" angezeigt werden. ――Es gibt andere Möglichkeiten, Deque als die Aufzählung von Zeichenfolgen / Zahlenzeichenfolgen zu verwenden. Daher ist es vorteilhaft, sich daran zu gewöhnen.
Die Wiederholung der Warteschlange ist die "Breitenprioritätssuche" (BFS) selbst. Die Stapelrekursion führt zu einer "Tiefenprioritätssuche" (DFS).
Sie können beides tun, wenn Sie nur alle Zeichenfolgen und Zahlen erstellen, die Reihenfolge, in der sie angezeigt werden, jedoch unterschiedlich ist.
Die letzte besteht darin, die im offiziellen Kommentar-PDF beschriebene Suche mit Tiefenpriorität zu verwenden. Verwenden Sie "rekursive Funktion".
Sie können viel mehr als nur eine Warteschlangen- oder Stapelaufklärung durchführen. Wenn Sie jedoch nur Zeichenfolgen oder Zahlen erstellen möchten, reicht die Rekursion der Warteschlange aus.
Der Vorteil der Tiefenprioritätssuche ist
――Einfache Implementierung von "Going Processing" und "Returning Processing" ――Ich habe das Gefühl, ich schreibe einen Algorithmus, wenn ich kann
Der Nachteil ist
--Retroaktive Funktionen sind schwer zu verstehen (nicht versuchen, fühlen und sich daran gewöhnen)
Das Argument der Funktion dfs ist die aktuelle Sequenz seq (taple). Die Untergrenze der nächsten Zahl ist seq [-1], da dies die letzte in der aktuellen Sequenz ist.
Angenommen, Sie addieren 3 zur Sequenz 1,1, um 1,1,3 zu erhalten. Die nächste hinzuzufügende Zahl muss 3 oder höher sein, daher ist (die Untergrenze der nächsten Zahl) die 3, die wir gerade hinzugefügt haben.
Wenn die Länge der aktuellen Nummernspalte kleiner als n ist, fügen Sie (untere Anzahlgrenze) zu (obere Grenze der Nummer m) hinzu und fügen Sie alle neuen Nummernspalten erneut zu dfs hinzu (aktuell erstellte Nummernfolge, jetzt erstellte Nummernspaltenlänge). Der Mindestwert der folgenden Zahlen).
Wenn die aktuelle Zahlenspalte 1,1,3 ist und die Obergrenze $ M = 4 $ ist, 1,1,3,3 1,1,3,4 Ist an dfs zu übergeben.
Wenn die Länge n ist und sie abgeschlossen ist, wird die Punktzahl berechnet. Wenn Sie eine Punktzahl erhalten, aktualisieren Sie den Maximalwert mit "ans = max (ans, score)". Dies entspricht einem normalen Problem.
Wenn alles erledigt ist, werden alle Maximalwerte im Code des Hauptteils zurückgegeben. Drucken Sie dies aus und Sie sind fertig.
def dfs(seq):
#Der Rückgabewert ist die maximale Punktzahl für alle Spalten.
ans = 0
if len(seq) == n:
#Nachdem die Sequenz abgeschlossen ist, berechnen Sie die Punktzahl
score_ret = 0
for a, b, c, d in req:
if seq[b-1] - seq[a-1] == c:
score_ret += d
return score_ret #Gibt die Punktzahl dieser Zahlenfolge zurück
else:
#Die Anzahl der Zeilen ist noch nicht abgeschlossen
for i in range(seq[-1], m + 1):
seq_next = seq + (i,) #Taple der Länge 1(i,)Verketten
score = dfs(seq_next) # seq_Gibt die maximale Punktzahl in allen von next abgeleiteten Sequenzen zurück
ans = max(ans, score) #Maximale Punktzahl aktualisieren
#Gibt die maximale Punktzahl zurück
return ans
n, m, q = list(map(int, input().split()))
#req ist[[a1,b1,c1,d1],[a2,b2,c2,d2]……]Es ist eine Liste der Liste, die enthält
req = [list(map(int, input().split())) for _ in range(q)]
#Stellen Sie sicher, dass Sie am Ende die Antwort erhalten. Die gesamte Verarbeitung erfolgt nach der dfs-Methode.
#Wenn es sich um eine Liste handelt, befürchte ich, dass ich den Wert versehentlich irgendwo neu schreiben werde, damit ich daraus einen Taple mache
#Sie müssen nicht darüber nachdenken, außer wenn der erste 1 ist.(1,)Ich werde nur tun
ans = 0
score = dfs((1,))
ans = max(ans, score)
print(ans)
Ich habe mehrmals geschrieben, dass ich nicht darüber nachdenken muss, außer wenn der erste in der Zahlenspalte 1 ist. Bei der Tiefenprioritätssuche von Code 3 wird tatsächlich nur der Anfang von 1 vollständig durchsucht.
Der Grund dafür ist, dass das "b-te Element und der a-te" Unterschied "wichtig sind und die Zahl selbst alles sein kann.
Zum Beispiel hat 2,3,3,4 den gleichen Unterschied wie 1,2,2,3 und 3,3,3,3 hat den gleichen Unterschied wie 1,1,1,1. Wie Sie sehen können, gibt es immer eine äquivalente Zahlenfolge ab 1 in einer anderen Reihenfolge als 1.
Sie können alles separat ausführen, aber wenn Sie es bemerken, ist die Implementierung möglicherweise etwas einfacher. Übrigens wird die Ausführungszeit halbiert, aber es spielt keine Rolle, da es nicht zu TLE wird, selbst wenn Sie alle Dateien außer dem Anfang durchsuchen.
Hier sind einige ähnliche Probleme. Das Hauptproblem ist genau der richtige Schwierigkeitsgrad, an den man sich gewöhnen kann. Die letzten beiden sind etwas schwieriger, aber immer noch einfacher als diese.
Braunstufe: ABC029 C - Brute-Force-Angriff Grüne Stufe: ABC161 D --Lunlun Number Grüne Stufe: Panasonic Programming Contest 2020 D - String Equivalence
Recommended Posts