** A-, B-, C-, D-Probleme ** des ** AtCoder Beginner Contest 183 ** 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.
Wenn Sie Fragen oder Anregungen haben, hinterlassen Sie bitte einen Kommentar oder Twitter. Twitter: u2dayo
[ABC183 Zusammenfassung](# abc183-Zusammenfassung) [Ein Problem "ReLU"](# ein Problem relu) [B Problem "Billard"](#b Problem Billard) [C Problem "Reisen"](#c Problem Reisen) [D Problem "Warmwasserbereiter"](#d Problem Warmwasserbereiter)
Gesamtzahl der Einreichungen: 7199
Performance | AC | Ergebnis | Zeit | Rangfolge(Innerhalb bewertet) |
---|---|---|---|---|
200 | AB---- | 300 | 32 Minuten | 5526(5365)Rang |
400 | ABC--- | 600 | 99 Minuten | 4586(4426)Rang |
600 | ABC--- | 600 | 38 Minuten | 3791(3632)Rang |
800 | ABCD-- | 1000 | 88 Minuten | 2963(2807)Rang |
1000 | ABCD-- | 1000 | 46 Minuten | 2194(2038)Rang |
1200 | ABCD-- | 1000 | 21 Minuten | 1554(1399)Rang |
1400 | ABCDE- | 1500 | 70 Minuten | 1060(911)Rang |
1600 | ABCDEF | 2100 | 122 Minuten | 700(557)Rang |
1800 | ABCDEF | 2100 | 77 Minuten | 440(315)Rang |
2000 | ABCDEF | 2100 | 59 Minuten | 273(164)Rang |
2200 | ABCDEF | 2100 | 46 Minuten | 161(78)Rang |
2400 | ABCDEF | 2100 | 37 Minuten | 100(35)Rang |
Farbe | Anzahl der Personen | A | B | C | D | E | F |
---|---|---|---|---|---|---|---|
Asche | 2960 | 99.5 % | 69.2 % | 35.0 % | 12.5 % | 1.9 % | 0.8 % |
Tee | 1377 | 99.7 % | 91.7 % | 87.5 % | 57.4 % | 5.8 % | 2.5 % |
Grün | 1086 | 99.6 % | 96.9 % | 97.0 % | 90.7 % | 26.4 % | 7.6 % |
Wasser | 664 | 99.8 % | 97.4 % | 99.5 % | 98.6 % | 69.7 % | 34.5 % |
Blau | 333 | 100.0 % | 99.7 % | 100.0 % | 100.0 % | 94.6 % | 76.0 % |
Gelb | 124 | 95.2 % | 94.3 % | 94.3 % | 95.2 % | 96.0 % | 91.9 % |
Orange | 28 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 96.4 % |
rot | 9 | 88.9 % | 88.9 % | 88.9 % | 88.9 % | 88.9 % | 100.0 % |
Es war ein blauer Kodierer ** für nur ** 23 Stunden.
** Problemseite **: A --ReLU ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 99,5% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 99,7% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 99,6%
Die ReLu-Funktion ist eine Funktion, die häufig als Übertragungsfunktion für tiefes Lernen verwendet wird.
x = int(input())
if x >= 0:
print(x)
else:
print(0)
** Problemseite **: B - Billard ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 69,2% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 91,7% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 96,9%
$ G_x --S_x = T_x $, $ S_y + G_y = T_y $. Aus dem offiziellen Kommentardiagramm können Sie sich das Dreieck unten vorstellen.
Die folgende Beziehung gilt aus der Ähnlichkeit und dem Verhältnis von Dreiecken.
Δx = \frac{S_y}{T_y}・ T._x
Die Antwort lautet $ S_x + Δx $, da $ Δx $ die Länge von $ S_x $ bis zum Reflexionspunkt an der Wand ist. Beachten Sie, dass $ T_x $ und $ Δx $ negativ sind, wenn sich das Ziel auf der linken Seite befindet (minus Richtung der $ x $ -Achse). Daher ist es nicht erforderlich, Fälle zu trennen.
sx, sy, gx, gy = map(int, input().split())
tx = gx - sx
ty = sy + gy
dx = tx * sy / ty
print(sx + dx)
** Problemseite **: C --Travel ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 35,0% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 87,5% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 97,0%
** * Es ist einfacher zu verstehen, ob es mit dem Index des Arrays übereinstimmt, daher beginnen wir bei der Stadt $ 0 $. ** ** **
Die Stadt $ 0 $ am Anfang und die Stadt $ 0 $ am Ende sind festgelegt, egal in welcher Reihenfolge Sie die Stadt besuchen.
Es gibt insgesamt $ (N-1)! $ Möglichkeiten, die Stadt von $ 1 $ bis $ N -1 $ zu besuchen. Das Maximum ist $ N = 8 $, es gibt also nur $ 7! = 5040 $.
** Daher reicht es aus, alle Besuchsaufträge auszuprobieren und die Anzahl der Dinge zu zählen, die nur $ K $ betragen. ** ** **
Wenn Sie alle möglichen Sequenzen in Python generieren möchten, verwenden Sie die "Permutationen" des "itertools" -Moduls.
In dieser Ausgabe möchte ich alle Sequenzen erstellen, die nach "(1, 2, 3, ..., N -1)" sortiert werden können. Übergeben Sie dazu "range (1, N)" als Argument für "permutations".
Insbesondere können Sie wie folgt schreiben.
for per in permutations(range(1, N)):
#wird bearbeitet
from itertools import permutations
N, K = map(int, input().split())
T = []
for _ in range(N):
s = list(map(int, input().split()))
T.append(s)
ans = 0
for per in permutations(range(1, N)):
score = 0 #Es ist die Zeit, die in der Reihenfolge dieses Besuchs benötigt wird
prev = 0 #Starten Sie zuerst von Stadt 0
for i in range(N - 1):
cur = per[i]
score += T[prev][cur] #Kopf von Stadt vorherr zu Stadt cur
prev = cur
score += T[prev][0] #Zum Schluss gehe in die Stadt 0
if score == K:
#Wenn Sie nur mit K umgehen können, ist die Antwort+1
ans += 1
print(ans)
** Problemseite **: D --Water Heater ** <font color = # 808080> Grau </ font> Richtige Antwortrate des Codierers **: 12,5% ** <font color = # 804000> Brown </ font> Richtige Antwortrate des Codierers **: 57,4% ** <font color = # 008000> Grün </ font> Richtige Antwortrate des Codierers **: 90,7%
Die Zeiten sind durch ganze Zahlen getrennt und haben ein Maximum von 200.000 US-Dollar. Erwägen Sie daher, ein Array zu erstellen, das die pro Stunde verbrauchte Warmwassermenge aufzeichnet. Natürlich reicht es nicht aus, jedem Abschnitt von $ N $ Leuten $ P_i $ hinzuzufügen.
Daher verwenden wir die kumulative Summe. ** "Addiere $ P_i $ von $ S_i $ zu $ T_i --1 $" ** kann auf diese Weise umschrieben werden.
Wenn Sie nur die erste Operation mit der üblichen kumulierten Summe ausführen, wird $ P_i $ nach $ T_i $ hinzugefügt. Wenn Sie also $ P_i $ nach $ T_i $ subtrahieren, um es abzubrechen, können Sie das Intervall um die kumulative Summe addieren.
Führen Sie diese $ 2 $ -Operationen mit einer Gruppe von jeweils $ 1 $ Personen durch. Suchen Sie schließlich die kumulierte Summe und prüfen Sie, ob der Warmwasserverbrauch jederzeit unter $ W $ liegt. Zu diesem Zweck können Sie mit der Funktion "max" bestimmen, ob die maximale kumulative Summe kleiner oder gleich $ W $ ist.
Beachten Sie, dass der in dieser Ausgabe verwendete ** "Algorithmus, der Intervalle unter Verwendung der kumulierten Summe" ** hinzufügt, manchmal als ** imos-Methode ** aus dem Namen des Entwicklers bezeichnet wird. Wenn Sie dies für ein eindimensionales Array tun, ist es ein einfacher Algorithmus, der nur die kumulative Summenoperation $ 2 $ mal ausführt.
Aus dem Kommentar von @ c-yan geht hervor, dass die Verwendung der Funktion "max" für die endgültige Beurteilung verbessert wurde. Vielen Dank!
from itertools import accumulate
C = 200005 #Die Länge C der kumulativen Summenfolge. Stellen Sie die Zahl entsprechend größer als 200.000 ein.
N, W = map(int, input().split())
seq_a = [0] * C
for _ in range(N):
s, t, p = map(int, input().split())
seq_a[s] += p
seq_a[t] -= p
S = list(accumulate(seq_a))
if max(S) <= W:
print('Yes')
else:
print('No')
Recommended Posts