** A, B, C Probleme ** des ** AtCoder Beginner Contest 180 ** werden mit ** Python3 ** so sorgfältig wie möglich erklärt.

Ich möchte eine Lösung erklären, die die folgenden drei Punkte erfüllt, nicht nur eine Methode, die gelöst werden kann.

Einfach: Sie müssen an nichts extra denken
Einfach zu implementieren: Ich bin froh, dass es weniger Fehler und Bugs gibt ――Es dauert nicht lange: Die Leistung steigt und Sie haben mehr Zeit für spätere Probleme.

Wenn Sie Fragen oder Anregungen haben, hinterlassen Sie bitte einen Kommentar oder Twitter. Twitter: u2dayo

Inhaltsverzeichnis

[ABC180 Zusammenfassung](# abc180-Zusammenfassung) [Eine Problembox "](# eine Problembox) [B Problem "Verschiedene Entfernungen"](#b Problem variable Entfernungen) [C Problem "Windbeutel"](#c Problem Windbeutel)

ABC180 Zusammenfassung

Gesamtzahl der Einreichungen: 5748

Performance

Performance	AC	Ergebnis	Zeit	Rangfolge(Innerhalb bewertet)
200	A-C---	400	Ein halbe Stunde	4393(4250)Rang
400	ABC---	600	51 Minuten	3638(3499)Rang
600	ABC---	600	23 Minuten	3008(2869)Rang
800	ABCD--	1000	115 Minuten	2357(2219)Rang
1000	ABCD--	1000	62 Minuten	1749(1614)Rang
1200	ABCD--	1000	23 Minuten	1241(1110)Rang
1400	ABCDE-	1500	85 Minuten	850(724)Rang
1600	ABCDE-	1500	60 Minuten	565(441)Rang
1800	ABCDE-	1500	44 Minuten	364(251)Rang
2000	ABCDE-	1500	33 Minuten	227(131)Rang
2200	ABCDE-	1500	26 Minuten	136(63)Rang
2400	ABCDE-	1500	17 Minuten	83(29)Rang

Richtige Antwortrate nach Farbe

Farbe	Anzahl der Personen	A	B	C	D	E	F
Asche	2412	99.0 %	68.4 %	64.4 %	12.4 %	1.2 %	0.0 %
Tee	1093	99.5 %	92.5 %	93.7 %	45.6 %	7.0 %	0.2 %
Grün	889	99.9 %	97.6 %	99.0 %	79.0 %	31.6 %	0.1 %
Wasser	544	100.0 %	99.8 %	99.8 %	95.8 %	73.2 %	0.7 %
Blau	268	100.0 %	99.6 %	99.6 %	97.8 %	94.0 %	6.3 %
Gelb	109	98.2 %	97.2 %	99.1 %	98.2 %	91.7 %	26.6 %
Orange	26	100.0 %	100.0 %	100.0 %	96.2 %	96.2 %	69.2 %
rot	8	62.5 %	62.5 %	62.5 %	62.5 %	75.0 %	100.0 %

Anzeigerate, Asche enthält keine Erstteilnehmer </ font>

Kurzer Kommentar

Ein Problem (5699 Personen AC) "Box"

Es ist in Ordnung, wenn Sie den Code für Addition und Subtraktion schreiben.

B-Problem (4683 Personen AC) "Verschiedene Entfernungen" Verwenden Sie die

for-Schleife, um sie genau so zu finden, wie sie geschrieben wurde.

C-Problem (4585 Personen AC) "Windbeutel"

Dies ist ein Problem bei der Ausgabe der Brüche in aufsteigender Reihenfolge. Die Aufzählung von Brüchen kann mit $ O (N) $ erfolgen.

D-Problem (2471 AC) "Takahashi Unevolved" [in diesem Artikel nicht erklärt] Während

$ A $ verdoppelt werden sollte, multiplizieren Sie tatsächlich $ A $, um zu simulieren. Wenn es besser ist, $ B $ hinzuzufügen, berechnen und ermitteln Sie die Anzahl der verbleibenden Male. Ab $ 2 ^ {60}> 10 ^ {18} $ beträgt die Anzahl der Multiplikationen von $ A $ höchstens $ 60 $.

E Problem (1189 Personen AC) "Reisender Verkäufer zwischen Luftstädten" [in diesem Artikel nicht erklärt]

Die Kosten zwischen den Städten betragen höchstens $ 17 ^ 2 = 375 $, und es ist leicht zu finden, also finden Sie es zuerst. Dann wird es nur ein Problem für reisende Verkäufer. Das Problem des Handlungsreisenden ist $ O (N!) $ Wenn alle Routen ausprobiert werden, jedoch die sogenannte dynamische Planungsmethode ** bitDP ** verwendet wird, $ O (N ^ {2} 2 ^ {N}) $ Kann mit gelöst werden.

F-Problem (80 Personen AC) "Unverzweigt" [in diesem Artikel nicht erklärt]

Es scheint eine dynamische Planungsmethode zu sein. Wie der Problemname andeutet, verzweigt sich das Diagramm nicht.

Ergebnisse von mir (Unidayo) (Referenz)

screenshot.266.png

Da ich angewandte Informationen studiert habe, handelt es sich um eine virtuelle Teilnahme.

Ein Problem "Box"

** Problemseite **: A --box

Erwägung

Sie müssen nicht über den Fall nachdenken, in dem der Versuch, $ A $ abzurufen, nicht ausreicht. Dies liegt daran, dass es nicht in der Problemstellung geschrieben ist und die Einschränkung $ A \ le {100} \ le {N} $ ist.

Daher ist $ N-A + B $ die Antwort.

Code

N, A, B = map(int, input().split())
print(N - A + B)

Problem B "Verschiedene Entfernungen"

** Problemseite **: B - Verschiedene Entfernungen

Erwägung

Die Formel zur Berechnung der Entfernung ist in der Problemstellung geschrieben. Auch wenn Sie die Bedeutung der Entfernung nicht verstehen, können Sie sie genau so berechnen, wie sie geschrieben steht. (Übrigens ist es unmöglich, konkret über die Entfernung jenseits der $ 4 $ -Dimension nachzudenken.)

Die Bedeutung jeder Formel ist wie folgt.

1. Manhattan Entfernung

『 x_iAbsolutwert von|x_i|] Ist die Summe (total).

2. Euklidischer Abstand

Die Quadratwurzel der Summe von "$ x_i $ im Quadrat $ {x_i} ^ {2} $". Wenn Sie einen negativen Wert quadrieren, ist dieser positiv, sodass Sie den absoluten Wert entfernen können.

Auf den ersten Blick mag es schwierig erscheinen, aber es wird $ \ sqrt {x ^ 2 + y ^ 2} $ in der Dimensionsebene $ 2 $ und $ \ sqrt {x ^ 2 + y ^ 2 + z ^ 2} $ im Dimensionsraum $ 3 $ sein. .. Dies ist die normale Distanz, die Sie in der Mathematik der Mittel- oder Oberstufe lernen.

3. Chebyshev Entfernung

『x_iAbsolutwert von|x_i|] Ist der Maximalwert.

Implementierung

Erstellen Sie die Variablen first, second_temp, Third mit einem Anfangswert von $ 0 $. Es entspricht "Manhattan-Entfernung", "Inhalt der Quadratwurzel der euklidischen Entfernung" und "Chevishev-Entfernung" in der Reihenfolge der Ausgabe.

Schauen Sie sich die Elemente der Liste der Punktkoordinaten X in einer for-Schleife an, jeweils $ 1 $, und berechnen Sie diese $ 3 $.

Verarbeitung in der for-Schleife

Dies ist der Prozess, der in der for-Schleife ausgeführt wird.

Die $ 1 $ -te "Manhattan-Entfernung" ist "first + = abs (x)", da Sie die absoluten Werte addieren können.

Der $ 2 $ -te "Inhalt der Quadratwurzel des euklidischen Abstands" kann zum Quadrat hinzugefügt werden, also ist es "second_temp + = x ** 2".

Der $ 3 $ -te "Chevishev-Abstand" ist "dritter = max (dritter, abs (x))", da der maximale absolute Wert aktualisiert werden sollte.

Post-Loop-Verarbeitung

Nehmen Sie die "zweite" Route, um die "euklidische Entfernung" zu ermitteln. Das heißt, "second = second_temp ** 0.5".

Da alle angefordert wurden, wird die Ausgabe in der Reihenfolge "zuerst", "zweitens", "drittens" und "Ende" ausgeführt.

Code

Sie müssen sich in Python keine Sorgen machen, aber second_temp kann so groß wie $ 10 ^ {15} $ sein. In C ++ usw. müssen Sie beim Überlauf vorsichtig sein.

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

first, second_temp, third = 0, 0, 0

for x in X:
    first += abs(x)
    second_temp += x ** 2
    third = max(third, abs(x))

second = second_temp ** 0.5

print(first)
print(second)
print(third)

Bonus

Sie müssen das nicht tun, aber Sie können auch die Funktionen höherer Ordnung (Funktionen, die eine Funktion als Argumente verwenden) map und redu verwenden, um sie jeweils in einer $ 1 $ -Zeile zu finden.

#Vielleicht gibt es einen besseren Weg zu schreiben
N = int(input())
X = list(map(int, input().split()))

print(sum(map(abs, X)))
print((sum(map(lambda x: x ** 2, X))) ** 0.5)
print(max(map(abs, X)))

C Problem "Windbeutel"

** Problemseite **: C - Cremepuff

Bedeutung des Problems

Geben Sie die Brüche von $ N $ in aufsteigender Reihenfolge aus.

Erwägung

Windbeutel können bis zu $ 10 ^ {12} $ kosten, daher reicht es nicht aus, alles von $ 1 $ bis $ 10 ^ {12} $ zu probieren.

Übrigens bedeutet ** "die Anzahl der Personen, die Windbeutel gleichmäßig teilen können, ohne sie zu teilen" ** ** "die durch $ N $ teilbare Zahl **".

** "Eine durch eine ganze Zahl $ N $ teilbare Zahl" ** heißt ** "ein Bruchteil von $ N $" **.

** Die Aufzählung von Brüchen kann mit $ O (\ sqrt {N}) $ erfolgen. ** $ \ sqrt {10 ^ {12}} = 10 ^ 6 , es ist also pünktlich. ( 10 ^ 6 $ sind $ 100 $ Millionen)

Effiziente Methode zur Aufzählung von Reduzierungen

Die Eigenschaften der Brüche sind ** "Wenn Sie alle Brüche unter $ \ sqrt {N} $ kennen, können Sie $ N $ durch sie teilen, um alle Brüche über $ \ sqrt {N} $ zu finden" ** es gibt.

Unter Ausnutzung dieser Eigenschaft ** "Versuchen Sie, $ N $ tatsächlich durch $ \ sqrt {N} $ zu teilen, und wenn es teilbar ist, fügen Sie $ x $ und $ N / x $ zur Reduktionsliste hinzu" ** Sie können die Brüche mit $ O (\ sqrt {N}) $ aufzählen.

Detaillierter Grund

Angenommen, $ N $ hat einen Bruchteil von $ x $. Zu diesem Zeitpunkt ist $ \ frac {N} {x} $ immer ein Bruchteil von $ N $.

Das liegt daran, dass $ N \ div {\ frac {N} {x}} = N \ times {\ frac {x} {N}} = x $. Zum Beispiel ist $ 36 = 3 \ times {12} $ ein Bruchteil von $ 36 $ für $ 3 $ und $ 12 $.

Wir werden solche $ x $ und $ \ frac {N} {x} $ ** "ein Paar von Brüchen" ** nennen. ** Ein "faires Paar" ist immer kleiner oder gleich $ \ sqrt {N} $ und das andere ist größer oder gleich $ \ sqrt {N} $. ** ** **

** Wenn es einen Bruch gibt, der größer oder gleich $ \ sqrt {N} $ ist, ist das Paar immer kleiner oder gleich $ \ sqrt {N} $. Daher können Sie die Brüche aufzählen, indem Sie $ N $ durch alle Brüche unter $ \ sqrt {N} $ teilen. ** ** **

Beweis

Ein "faires Paar" beweist immer, dass eines weniger als $ \ sqrt {N} $ und das andere mehr als $ \ sqrt {N} $ ist.

Es wird angenommen, dass beide kleiner als $ \ sqrt {N} $ sind, dh $ x \ lt {\ sqrt {N}} $ und $ \ frac {N} {x} \ lt {\ sqrt {N}} $.

Multiplikation der Ungleichung

x\times{\frac{N}{x}} < \sqrt{N}\times{\sqrt{N}}\\
N < N

Wird sein. Das ist seltsam, weil $ N = N $. Mit anderen Worten, die Annahme kann nicht falsch sein.

In ähnlicher Weise kann es kein "beides größer als $ \ sqrt {N} $" geben, wenn die Ungleichung umgekehrt ist.

Aus dem oben Gesagten geht hervor, dass eines der "fairen Paare" immer $ \ sqrt {N} $ oder weniger ist und das andere $ \ sqrt {N} $ oder mehr.

Implementierung

Grundsätzlich müssen Sie nur den folgenden Code schreiben.

divs = []

x = 1
while x ** 2 <= N:
    if N % x == 0:
        divs.append(x)
        divs.append(N // x)
    x += 1

Es gibt jedoch $ 2 $ Probleme mit diesem Code.

** Wenn $ \ sqrt {N} $ zu einem Bruch wird, wird $ \ sqrt {N} $ um $ 2 $ zur Liste hinzugefügt **

** Ergebnisse sind nicht in aufsteigender Reihenfolge **

Das $ 1 $ zweite Problem kann gelöst werden, indem der Fall geteilt wird, in dem $ \ sqrt {N} $ ein Bruchteil ist, aber es ist problematisch.

Wir werden ** set type ** verwenden, um Doppelarbeit zu vermeiden. Der Mengen-Typ ist ein Typ, der eine "ungeordnete Menge" behandelt und nur $ 1 $ für dasselbe Element enthält. Wenn Sie ein bereits vorhandenes Element hinzufügen, geschieht nichts.

Das $ 2 $ -Problem kann durch Sortieren gelöst werden. Der Set-Typ hat jedoch nicht das Konzept der Reihenfolge und kann nicht sortiert werden. In eine Liste konvertieren und dann sortieren.

Code

N = int(input())
divs = set()  #Verwenden Sie set, um Doppelarbeit zu vermeiden

#Mathematisch x<= N ** 0.Wie 5, jedoch sicherer im Vergleich zu fehlerfreien Ganzzahlen
x = 1
while x ** 2 <= N:
    if N % x == 0:
        divs.add(x)  #Zum Set hinzufügen ist hinzufügen, nicht anhängen
        divs.add(N // x)
    x += 1

ans = list(divs)  #Ich möchte in aufsteigender Reihenfolge sortieren, also eine Liste erstellen und sortieren
ans.sort()

for x in ans:
    print(x)

[AtCoder Erklärung] Kontrollieren Sie ABC180 A, B, C Probleme mit Python!

Inhaltsverzeichnis

ABC180 Zusammenfassung

Performance

Richtige Antwortrate nach Farbe

Kurzer Kommentar

Ergebnisse von mir (Unidayo) (Referenz)

Ein Problem "Box"

Erwägung

Code

Problem B "Verschiedene Entfernungen"

Erwägung

1. Manhattan Entfernung

2. Euklidischer Abstand

3. Chebyshev Entfernung

Implementierung

Verarbeitung in der for-Schleife

Post-Loop-Verarbeitung

Code

Bonus

C Problem "Windbeutel"

Bedeutung des Problems

Erwägung

Effiziente Methode zur Aufzählung von Reduzierungen

Implementierung

Code