[AtCoder Erklärung] Kontrollieren Sie ABC184 A, B, C Probleme mit Python!
** AtCoder Beginner Contest 184 ** ** A, B, C Probleme ** werden mit ** Python 3 ** 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
[ABC184 Zusammenfassung](# abc184-Zusammenfassung) [Ein Problem "Determinante"](# eine Problemdeterminante) [B Problem "Quiz"](# B Problem Quiz) [C Problem "Super Ryuma"](#c Problem Super-Ryuma)
ABC184 Zusammenfassung
Gesamtzahl der Einreichungen: 7822
Performance
| Performance | AC | Ergebnis | Zeit | Rangfolge(Innerhalb bewertet) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 12 Minuten | 5984(5769)Rang |
| 400 | AB---- | 300 | 6 Minuten | 4983(4768)Rang |
| 600 | AB---- | 300 | 4 Minuten | 4132(3917)Rang |
| 800 | ABC--- | 600 | 88 Minuten | 3271(3056)Rang |
| 1000 | ABC--- | 600 | 37 Minuten | 2454(2240)Rang |
| 1200 | ABCD-- | 1000 | 105 Minuten | 1767(1556)Rang |
| 1400 | ABC--F | 1200 | 97 Minuten | 1229(1026)Rang |
| 1600 | ABCD-F | 1600 | 66 Minuten | 832(636)Rang |
| 1800 | ABCDEF | 2100 | 97 Minuten | 551(367)Rang |
| 2000 | ABCDEF | 2100 | 73 Minuten | 352(195)Rang |
| 2200 | ABCDEF | 2100 | 57 Minuten | 228(96)Rang |
| 2400 | ABCDEF | 2100 | 45 Minuten | 130(44)Rang |
Richtige Antwortrate nach Farbe
| Farbe | Anzahl der Personen | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| Asche | 3253 | 98.7 % | 92.0 % | 15.3 % | 2.3 % | 1.0 % | 0.7 % |
| Tee | 1499 | 99.3 % | 99.1 % | 45.8 % | 9.5 % | 4.9 % | 4.5 % |
| Grün | 1184 | 99.5 % | 99.5 % | 63.4 % | 29.6 % | 18.4 % | 14.1 % |
| Wasser | 729 | 99.9 % | 99.9 % | 78.5 % | 58.7 % | 49.1 % | 54.6 % |
| Blau | 360 | 99.7 % | 99.7 % | 94.4 % | 88.6 % | 86.1 % | 88.1 % |
| Gelb | 175 | 96.0 % | 96.0 % | 93.1 % | 94.3 % | 91.4 % | 96.6 % |
| Orange | 31 | 96.8 % | 96.8 % | 96.8 % | 96.8 % | 96.8 % | 96.8 % |
| rot | 11 | 90.9 % | 90.9 % | 90.9 % | 90.9 % | 100.0 % | 100.0 % |
- Anzeigerate, Asche enthält keine Erstteilnehmer </ font>
Kurzer Kommentar
- Ein Problem (7738 Personen AC) "Determinante"
- Auch wenn Sie den Matrixausdruck nicht kennen, können Sie tun, was Ihnen gesagt wurde.
- B-Problem (7439 Personen AC) "Quiz"
- Es ist in Ordnung, wenn Sie es gehorsam simulieren.
- C-Problem (3137 Personen AC) "Super Ryuma"
- Ich bin mir nicht sicher, daher ist es eine gute Idee, zu versuchen, wie viele Züge Sie jedes Quadrat in einem kleinen Raster erreichen können, um die Regeln zu finden. Das Schreiben auf Papier ist mühsam und fehleranfällig. Daher ist es eine gute Idee, ein Programm zu erstellen, das einfache Antworten ausgibt.
- D Problem (1561 Personen AC) "Inkrement von Münzen" [in diesem Artikel nicht erklärt]
- Es ist eine Wahrscheinlichkeit DP.
- E Problem (1223 AC) "Third Avenue" [in diesem Artikel nicht erklärt]
- Die Suche nach Breitenpriorität wird durchgeführt.
- F-Problem (1209 Personen AC) "Programmierwettbewerb" [in diesem Artikel nicht erklärt]
- Ich mache nur "halb vollständige Aufzählung" ohne besonderen Aufwand.
- $ x $ Koordinaten sind $ + k $, $ y $ Koordinaten sind $ + k $ (oben rechts)
- $ x $ Koordinaten sind $ + k $, $ y $ Koordinaten sind $ -k $ (unten rechts)
- $ x $ Koordinaten sind $ -k $, $ y $ Koordinaten sind $ + k $ (oben links)
- $ x $ Koordinaten sind $ -k $, $ y $ Koordinaten sind $ -k $ (unten links)
Ergebnisse von mir (Unidayo) (Referenz)
Ein Problem "Determinante"
** Problemseite **: A --Determinant ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 98,7% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 99,3% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 99,5%
Auch wenn Sie die Matrixformel nicht kennen, können Sie sie genau so ausführen, wie sie geschrieben steht.
Code
A, B = map(int, input().split()) C, D = map(int, input().split()) print(A * D - B * C)B Problem "Quiz"
** Problemseite **: B - Fragen ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 92,0% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 99,1% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 99,5%
Implementierung
Es ist in Ordnung, wenn Sie die for-Schleife gehorsam verwenden und sie gemäß der Problemstellung implementieren. Wenn Sie Klarheit priorisieren, ohne zu versuchen, sie auf coole Weise zu schreiben, können Sie Fehler reduzieren.
Code
N, X = map(int, input().split()) S = input() score = X for char in S: if char == "o": score += 1 else: if score > 0: score -= 1 print(score)C Problem "Super Ryuma"
** Problemseite **: C - Super Ryuma ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 15,3% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 45,8% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 63,4%
Bedeutung des Problems
$ 1 $ Es gibt ein Stück "Super Ryoma", mit dem Sie eine der folgenden Bewegungen mit Ihren Händen ausführen können.
** - Bewege deine Lieblingsmasse diagonal (genau wie die Ecke eines Shogi. Wir nennen es ** diagonale Bewegung **) ** ** - Dreimal nach oben, unten, links und rechts drehen ("Manhattan-Entfernung" kann sich innerhalb von $ 3 $ zu einem Quadrat bewegen. Wir nennen es ** Super Ryoma-Bewegung **) **
Da die Start- und Zielkoordinaten angegeben sind, geben Sie bitte aus, wie viele Züge Sie in "Super Ryoma" ausführen können.
Erwägung
Es scheint, dass es nicht viel Sinn macht. ** Ich bin mir nicht sicher, daher möchte ich vorerst ein Programm schreiben, das die Anzahl der Bewegungen, um die Regel zu finden, ehrlich berechnet und ausgibt. Sie können es auf Papier schreiben, aber es ist einfacher und weniger fehleranfällig, es zu programmieren. ** (Als Referenz habe ich 5 $ ausgegeben, um diesen Code zu schreiben, und ich hatte große Probleme, ihn während des Wettbewerbs auf Papier zu schreiben.)
def change(a, b, p): for c in range(K): for d in range(K): if (a + b) == (c + d) or (a - b) == (c - d) or (abs(a - c) + abs(b - d)) <= 3: if grid[c][d] == -1: grid[c][d] = p + 1 K = 41 grid = [[-1] * K for _ in range(K)] grid[K // 2][K // 2] = 0 for i in range(10): for a in range(K): for b in range(K): if grid[a][b] == i: change(a, b, i) for row in grid: print(*row)Dann sieht die Ausgabe so aus.
1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 1 1 1 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 0 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 1 1 1 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1** Anscheinend habe ich das Gefühl, dass ich es mit maximal $ 3 $ verschieben kann. Überlegen wir uns also, warum dies passiert. ** ** **
Angenommen, Sie haben ein schwarz-weißes Schachbrett und beginnen mit einem schwarzen Quadrat. ** Diagonal bewegen $ 2 $ Sie können von Hand zu jedem schwarzen Quadrat auf dem Schachbrett gehen. Es ist jedoch nicht möglich, sich nur diagonal zu einem weißen Quadrat zu bewegen. Wenn das Ziel ein weißes Quadrat ist, können Sie es um $ 2 $ auf das schwarze Quadrat direkt neben dem Ziel verschieben und dann um $ 1 $ verschieben. Auf diese Weise können Sie für weniger als $ 3 $ zu einem beliebigen Feld auf dem Schachbrett wechseln. ** Aus diesem Grund sind $ 2 $ und $ 3 $ wie ein Schachbrett angeordnet. (Offizieller Kommentar hat ebenfalls eine Zahl)
Nachdem wir nun wissen, dass wir nur an $ 3 $ denken müssen, betrachten wir die bedingten Ausdrücke, die bestimmen, wie viele Hände wir haben werden.
Wenn Sie 0 Hände bekommen
Sie müssen sich nicht nur bewegen, wenn sich Start und Ziel am selben Ort befinden. Bitte legt er einen $ 0 $ Handkoffer in die Probe.
Wenn du eins bekommst
Sie können $ 1 $ natürlich von Hand bewegen, wenn Sie sich um $ 1 $ bewegen können. (?) $ 1 $ Die Bedingungen für einen Ort, an dem Sie sich von Hand bewegen können, sind in der Problembeschreibung angegeben. Wenn Sie also einen der $ 3 $ erfüllen, können Sie sich um $ 1 $ bewegen.
a+b = c+d a-b = c-d |a-c| + |b-d| \le{3} Wenn Sie zwei Hände haben
Ist schwierig. Zunächst erinnere ich mich, dass "Super Ryoma" $ 2 $ bewegen kann.
** - Diagonale Bewegung ** ** - Super Ryoma Move **
Die $ 2 $ Handbewegung ist eine Kombination der $ 2 $ Bewegungsarten. Es gibt die folgenden $ 3 $ Muster zum Kombinieren.
** - Super Ryoma bewegen sich $ 2 $ mal ** ** - Diagonale Bewegung $ 2 $ mal ** ** - Diagonale Bewegung $ 1 $ mal und Super Ryoma Bewegung $ 1 $ mal **
Super Ryoma Zug 2 Züge
Super Ryoma Move $ 1 $ Sie können $ 1 $ Quadrate 3 $ Mal pro Hand nach oben, unten, links und rechts $ bewegen. Mit anderen Worten, Sie können den Super Ryoma $ 2 $ 6-mal von Hand nach oben, unten, links und rechts bewegen.
** Einfach ausgedrückt, wenn die "Manhattan-Entfernung" weniger als 6 $ beträgt, können Sie sie um 2 $ verschieben. Daher ist die Bedingung wie folgt. ** ** **
|a-c|+|b-d|\le{6} Diagonale Bewegung 2 Hände
Sie können sich im Beispiel des Schachbretts überall in der "Masse der gleichen Farbe wie der Startpunkt" bewegen. Lassen Sie uns etwas genauer darüber nachdenken, um es in die Formel aufzunehmen.
Diagonale Bewegung $ 1 $ Von Hand ändern sich die Koordinaten wie folgt:
Daher beträgt die Summe der Änderungen der $ x $ - und $ y $ -Koordinaten entweder $ + 2k $, $ 0 $ oder $ -2k $. ** Beachten Sie, dass die Summe der Änderungen immer gerade ist. Dies bedeutet, dass unabhängig davon, wie oft Sie sich diagonal bewegen, die Summe der Änderungen niemals in einem ungeraden Quadrat endet. (Dieses Konzept heißt Parität / gerade / ungerade) **
Wenn andererseits die Summe der Änderungen gerade ist, können Sie sie von Hand erreichen, egal wie weit sie entfernt ist.
|a-c| + |b-d|Ist gerade (der Rest nach Division durch 2 ist 0) - Diagonale Bewegung $ 1 $ Hand und Super Ryoma Bewegung $ 1 $ Hand
Diagonale Bewegung $ 1 $ Die Zellen, die von Hand bewegt werden können, sind solche mit $ a + b = c + d $ oder $ a-b = c-d $. Bei der Transponierung ist $ (a + b) - (c + d) = 0 $ und $ (a-b) - (c-d) = 0 $.
Von einem Quadrat, das diese Bedingung erfüllt, können Sie Super Ryoma von Hand auf ein Quadrat mit einem Manhattan-Abstand von 3 USD oder weniger verschieben.
|(a+b)-(c+d)|\le{3} |(a-b)-(c-d)|\le{3} Wenn Sie 3 Hände bekommen
$ 0 $ ~ $ 2 $ Wenn Sie es nicht von Hand bewegen können, sind es $ 3 $. Es besteht keine Notwendigkeit zu urteilen.
Implementierung
Schreiben Sie alle bedingten Ausdrücke. Es ist einfacher, den Beurteilungsteil in Funktionen zu unterteilen und den Moment zurückzugeben, in dem die Bedingungen erfüllt sind.
Bitte beachten Sie, dass die richtige Antwort nur erhalten wird, wenn Sie in der Reihenfolge $ 0 $ Hand, $ 1 $ Hand, $ 2 $ Hand, $ 3 $ Hand von der mit der geringsten Anzahl von Schritten urteilen.
Code
def solve(): #0 Hände. Wenn Sie das Beispiel nicht richtig betrachten, werden Sie dieses Muster vergessen. if a == c and b == d: return 0 #Es ist ein Zug. Schreiben Sie gemäß der Problemstellung. if a + b == c + d: return 1 if a - b == c - d: return 1 if abs(a - c) + abs(b - d) <= 3: return 1 #Zwei Züge. Schreiben Sie wie betrachtet. if abs(a - c) + abs(b - d) <= 6: return 2 if (abs(a - c) + abs(b - d)) % 2 == 0: # %Da die Priorität von hoch ist, fügen Sie die linke Seite hinzu()Wenn Sie es nicht beilegen, ist es WA (1 Verlust) return 2 if abs((a + b) - (c + d)) <= 3: return 2 if abs((a - b) - (c - d)) <= 3: return 2 #Wenn Sie es nicht mit 2 Zügen machen können, müssen Sie 3 Züge haben. return 3 a, b = map(int, input().split()) c, d = map(int, input().split()) print(solve())Recommended Posts