Diese Seite wurde hauptsächlich für Python-Benutzer erstellt, die der Meinung sind, dass A- und B-Probleme des AtCoder Beginner Contest (ABC) gelöst werden können, das C-Problem jedoch schwierig ist, beginnend mit AtCoder. Hat. Wir haben die Ideen zu Einschränkungen und den Umfang der Berechnung sowie die Ideen, die Sie basierend auf den Einschränkungen und dem Umfang der Berechnung kennen sollten, kurz zusammengefasst.
Wenn Sie mehrmals an ABC teilgenommen haben, haben Sie möglicherweise den Kommentar mit Berechnungsaufträgen wie ** $ O (N ^ 2) $ ** und ** $ O (NlogN) $ ** gesehen. Es kann sein. Um ehrlich zu sein, gibt es viele Leute, die nicht verstehen, was sie bedeuten oder woher das Protokoll stammt, auch wenn dies geschrieben steht.
Diese Idee der berechneten Mengenbestellung ist die Seite von ** Kenchon-san **, die in der wettbewerbsorientierten Programmierwelt berühmt ist. ~ Woher kommt das Protokoll ~](https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0)
Sie können im Voraus grob abschätzen, wie lange die Berechnung dauern wird.
Es wird so sein.
Eine ausführliche Erläuterung der Reihenfolge der Berechnungsbeträge finden Sie auf der obigen Seite von Kenchon-san. Die Idee der Reihenfolge der Berechnungsbeträge ist jedoch die Berechnungsgeschwindigkeit. Kann geschätzt werden und wird nach dem C-Problem von ABC wichtig (insbesondere in Python). Lassen Sie uns grob über den Umfang der Berechnung nachdenken.
Um den Rechenaufwand kurz zu erläutern, ** "Mit zunehmender Eingabegröße ** $ n $ ** erhöht sich die Ausführungszeit proportional um diesen Betrag." ** Es wird ein Index.
Betrachten wir zunächst die folgenden Probleme anhand konkreter Beispiele.
Takahashi, ein Grundschüler im ersten Jahr, der gerne Zahlen hinzufügt, fügt immer 1 + 2 + 3 hinzu ... Irgendwann beschloss Takahashi, ganze Zahlen von 1 bis ** $ n $ ** hinzuzufügen. Was ist die Summe der ganzen Zahlen von 1 bis ** $ n $ **?
Dieses Problem kann durch einfaches Hinzufügen von 1 zu ** $ n $ ** gelöst werden. Das eigentliche Schreiben ist wie folgt.
python
n = int(input())
ans = 0
for i in range(1, n+1):
ans += i
print(ans)
Lassen Sie uns nun über den Rechenaufwand in diesem Code nachdenken, aber es ist einfach. Da es "1 + 2 + ..." und ** $ n $ ** Mal gedauert hat, wird der Berechnungsbetrag als ** $ O (N) $ ** angesehen. Dies bedeutet, dass mit zunehmender Eingabegröße ** $ n $ ** die Anzahl der Berechnungsschritte proportional zu ** $ n $ ** zunimmt.
Als nächstes betrachten wir die folgenden Probleme.
Takahashi, ein Grundschüler im zweiten Jahr, der es liebt, Zahlen zu multiplizieren, hat es satt, neunundneunzig zu berechnen. Daher erstellte Takahashi eine neue Neunundneunzig mit einer beliebigen natürlichen Zahl ** $ n $ ** und vertikalen / horizontalen ** $ n $ × $ n $ ** Quadraten. Die neuen neunundneunzig hat Schritte von 1, 2 ... ** $ n $ ** -1, ** $ n $ ** sowohl vertikal als auch horizontal, zum Beispiel ** (11, 10) ** Quadrate. Die Zahl in ist 11 × 10 und ist ** 110 **. Takahashi-kun, der die neuen neunundneunzig machte, erinnerte sich, dass er auch gerne hinzufügte, und beschloss, alle Zahlen in der Tabelle hinzuzufügen. Was ist die Summe?
Dieses Problem kann mithilfe der for-Anweisung in der for-Anweisung gelöst werden. Das eigentliche Schreiben ist wie folgt.
python
n = int(input())
ans = 0
for i in range(1, n+1):
for j in range(1, n+1):
ans += i * j
print(ans)
In Anbetracht des Berechnungsaufwands für diesen Code wird ** $ O (N ^ 2) $ **. Die Verwendung einer for-Anweisung in dieser for-Anweisung wird als Doppelschleife bezeichnet, und der Bewegungsfluss ist
python
# n = 100
# i =Wenn 1
ans += 1 * 1
ans += 1 * 2
ans += 1 * 3
Und wenn die zweite Schleife vorbei ist
python
# n = 100
# i =Wenn 1
ans += 1 * 99
ans += 1 * 100
# i =Werden Sie 2
ans += 2 * 1
ans += 2 * 2
... und weiter bis i = 100, j = 100. Auf diese Weise dauert die Anzahl der Schritte ** $ n × n $ ** mal, wobei der Rechenaufwand berücksichtigt wird. Mit zunehmender Eingabegröße ** $ n $ ** steigt die Anzahl der Berechnungsschritte proportional zu ** $ n ^ 2 $ **, was zu ** $ O (N ^ 2) $ ** führt.
Betrachten wir das nächste Problem in diesem Ablauf.
Takahashi, ein Grundschüler im dritten Jahr, beschloss, neunundneunzig zu machen, weil neunundneunzig nicht genug war. Neunundneunzig ist die Summe aus Länge, Breite und Höhe, und es gibt ** $ n $ × $ n $ × $ n $ ** Quadrate. Die Länge, Breite und Höhe sind beliebige natürliche Zahlen ** $ n $ **, und die Schritte sind 1, 2 ... ** $ n $ ** -1, ** $ n $ **. Die Zahlen in den Quadraten ** (3, 4, 9) ** sind 3 × 4 × 9, also ** 108 **. Takahashi-kun, der die neunundneunzig kreierte, erinnerte sich, dass er auch gerne hinzufügte, und beschloss, alle Zahlen in der Tabelle hinzuzufügen. Was ist die Summe?
Dieses Problem kann mit einer Dreifachschleife gelöst werden, die die for-Anweisung in der for-Anweisung verwendet und dann die for-Anweisung darin verwendet. Das eigentliche Schreiben ist wie folgt.
python
n = int(input())
ans = 0
for i in range(1, n+1):
for j in range(1, n+1):
for k in range(1, n+1):
ans += i * j * k
print(ans)
Wie Sie sehen können, wird der Rechenaufwand in diesem Code zu ** $ O (N ^ 3) $ **, und wenn die Eingabegröße ** $ n $ ** zunimmt, wird er zu ** $ n ^. Da die Anzahl der Berechnungsschritte proportional zu 3 $ ** zunimmt, wird sie zu ** $ O (N ^ 3) $ **.
Auf diese Weise beträgt der Berechnungsbetrag ** $ O (N) $ ** für eine for-Anweisung, ** $ O (N ^ 2) $ ** für eine Doppelschleife und ** $ für eine Dreifachschleife. Mit zunehmender Anzahl von Schleifen, wie z. B. O (N ^ 3) $ ** ..., steigt auch der Rechenaufwand.
Übrigens, wenn es nur zwei for-Anweisungen anstelle mehrerer Schleifen gibt, ist dies ** $ O (N) $ ** anstelle von ** $ O (N ^ 2) $ **. Dies liegt daran, dass bei Berücksichtigung des Rechenaufwands die andere Reihenfolge als die größte Reihenfolge entfernt und der Koeffizient ignoriert wird. Weitere Informationen finden Sie auf der Seite ** Kencho-san **, die zuvor vorgestellt wurde.
Fügen Sie die folgenden Codes 1 bis 100 zweimal hinzu. Tatsächlich ist diese Anzahl von Schritten 200-mal, und im Fall einer Doppelschleife sind 10.000 Schritte erforderlich, wenn n = 100 ist, so dass es sich wie ** $ von ** $ O (N ^ 2) $ ** anfühlt. Ich denke, O (N) $ ** ist vernünftig.
python
n = 100
ans = 0
for i in range(1, 101):
ans += i
for i in range(1, 101):
ans += i
print(ans)
Nachdem der Rechenaufwand in der for-Anweisung erforderlich ist, lassen Sie uns dies mit Einschränkungen betrachten.
Im eigentlichen Problem wird die Einschränkung immer wie folgt geschrieben.
Einschränkungen ・ ** $ 1 ≤ N ≤ 10 ^ 5 $ **
Mit dieser Einschränkung können Sie grob verstehen, ob der von Ihnen geschriebene Code das Zeitlimit einhält, indem Sie ihn als Berechnungsbetrag betrachten.
Zum Beispiel ist die Einschränkung ・ ** $ 1 ≤ N ≤ 10 ^ 7 $ ** Zu diesem Zeitpunkt kann dies übergeben werden, ohne das Zeitlimit zu überschreiten, wenn es sich um eine for-Anweisung von ** $ O (N) $ ** handelt. Im Fall von ** $ O (N ^ 2) $ ** wie einer Doppelschleife, die größer als ** $ O (N) $ ** ist, wird das Zeitlimit jedoch immer überschritten. (Weil die Anzahl der Schritte, die pro Sekunde verarbeitet werden können, ungefähr 10 $ ^ 8 $ ** mal beträgt)
Übrigens beträgt das Zeitlimit von ABC 2 Sekunden. Im Fall von ** $ O (N) $ ** ist es besser zu denken, dass ** $ N ≤ 10 ^ 7 $ ** das Limit ist.
Als nächstes kommt die Einschränkung ・ ** $ 1 ≤ N ≤ 10 ^ 5 $ ** Dies bedeutet dann, dass ** $ O (N) $ ** leicht übergeben werden kann und sogar ein Berechnungsbetrag wie ** $ O (NlogN) $ ** innerhalb des Zeitlimits übergeben werden kann (dazu später mehr). .. Im Fall von ** $ O (N ^ 2) $ ** kann es jedoch nicht übergeben werden, da es ** $ 10 ^ 8 $ ** als Richtwert überschreitet.
Und die Einschränkungen ・ ** $ 1 ≤ N ≤ 10 ^ 3 $ ** Zu diesem Zeitpunkt können Sie endlich den Berechnungsbetrag von ** $ O (N ^ 2) $ ** übergeben.
Es gibt auch Einschränkungen ・ ** $ 1 ≤ N ≤ 300 $ ** In diesem Fall können Sie auch den Berechnungsbetrag von ** $ O (N ^ 3) $ ** übergeben.
Sobald Sie den Umfang der Berechnung wie folgt kennen, können Sie grob prüfen, ob dieser Code innerhalb der Einschränkung übergeben werden kann. Python ist jedoch eine viel langsamere Sprache als andere Sprachen wie C ++, sodass die oben genannten Bedingungen möglicherweise nicht zutreffen. Tatsächlich war ABC162-C ein Problem der Dreifachschleife, aber die Einschränkung ist ** $ 1 ≤ N ≤ 200 $ **, und der Rechenaufwand beträgt Das Zeitlimit kann trotz ** $ O (N ^ 3logN) $ ** überschritten werden. (Es kann in anderen Sprachen übergeben werden.)
Auf diese Weise muss sich Python des Rechenaufwands bewusster sein als andere Sprachen.
Denken wir an das eigentliche Problem.
Denken wir zunächst an ABC154-C.
Das Problem ist, dass bei einem Array von ** $ n $ ** Ganzzahlen "YES" ausgegeben wird, wenn keine Duplikate vorhanden sind, und "NO", wenn Duplikate vorhanden sind. Wenn Sie einfach denken, können Sie die Antwort finden, indem Sie jedes Array einzeln mit einer Doppelschleife überprüfen.
python
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
for j in range(i+1, n):
if a[i] == a[j]:
print("NO")
exit()
print("YES")
Auf diese Weise wird bei doppelten Ganzzahlen "NO" ausgegeben und exit () verwendet. Wenn keine doppelten Ganzzahlen vorhanden sind, endet die Doppelschleife und "YES" wird ausgegeben. (Da es sich übrigens um eine Doppelschleife handelt, beträgt der Berechnungsbetrag ** $ O (N ^ 2) $ **)
Aber wenn Sie sich die Grenzen dieses Problems ansehen ・ ** $ 2 ≤ N ≤ 200000 $ ** In diesem Fall reicht ** $ O (N ^ 2) $ ** nicht aus.
Dann denke ich, dass mit dieser Einschränkung der Rechenaufwand mit ** $ O (NlogN) $ ** oder ** $ O (N) $ ** gelöst werden kann.
Wenn Sie das Array in aufsteigender oder absteigender Reihenfolge sortieren und doppelte Zahlen vorhanden sind, werden diese nebeneinander angezeigt. Sie werden also anscheinend nach einer Antwort gefragt, indem Sie nach dem Sortieren alle Werte nebeneinander überprüfen. In Python können Sie das Array mithilfe der Sortiermethode in aufsteigender oder absteigender Reihenfolge sortieren.
python
a = [5, 2, 3, 4, 3, 9]
a.sort() #aufsteigende Reihenfolge
# 2, 3, 3, 4, 5, 9
a.sort(reverse=True) # reverse=Wahr in absteigender Reihenfolge
# 9, 5, 4, 3, 3, 2
Da die Berechnungsmenge dieser Sortiermethode mit ** $ O (NlogN) $ ** durchgeführt werden kann, kann die Berechnungsmenge mit ** $ O (NlogN) $ ** durchgeführt werden, indem nach dem Sortieren die for-Anweisung überprüft wird. (Weil es ** $ O (NlogN + N) $ ** wird und nur die höchste Ordnung berücksichtigt wird)
Die tatsächliche Version ist wie folgt.
python
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n-1):
if a[i] == a[i+1]:
print("NO")
exit()
print("YES")
Wenn die Einschränkung ** $ 10 ^ 5 $ ** ist, ist es auf diese Weise einfacher, nach dem C-Problem zu berücksichtigen, wenn Sie sich bewusst sind, dass ** $ O (N ^ 2) $ ** nicht rechtzeitig ist. Ebenso wie diesmal bei der Sortiermethode muss bekannt sein, wie der Rechenaufwand reduziert werden kann.
Das Obige ist eine grobe Einführung der for-Anweisung, hauptsächlich über den Rechenaufwand. Wenn die for-Anweisung eine for-Anweisung enthält, beträgt der Berechnungsbetrag ** $ O (N ^ 2) $ ** und der Berechnungsbetrag der Sortiermethode ** $ O (NlogN) $ **. Sie werden sich vielleicht zuerst nicht daran gewöhnen, aber wenn Sie üben, werden Sie sich natürlich daran erinnern.
Abhängig vom Problem gibt es viele Möglichkeiten, den Rechenaufwand zu reduzieren, z. B. die lineare Suche in eine zweiminütige Suche zu ändern, um den Rechenaufwand zu reduzieren, oder die Teilsumme des Arrays mithilfe der Scooping-Methode oder der kumulativen Summe effizient zu ermitteln. Wenn Sie sich an diese Dinge erinnern, können Sie nach und nach das C-Problem von ABC lösen.
Um das C-Problem von ABC zu lösen, denke ich, dass der Schlüssel zur Hingabe darin besteht, viele frühere Fragen des C-Problems zu üben. Selbst wenn Sie AC selbst ausführen, können Sie eine andere Methode kennen, den Rechenaufwand in diesem Fall und wie Sie den Code schön schreiben, indem Sie die Erklärung oder den Code anderer lesen. Da es für jedes Problem leicht verständlich ist, verschiedene Erklärungen zu verfassen, sollten Sie die offizielle Erklärung oder den Code einer anderen Person lesen und herausfinden, welche Art von Überlegungen Sie anstellen sollten.
Das Ende ist chaotisch geworden, aber dieser Artikel ist vorbei. Danke für deine harte Arbeit!