[AtCoder-Erklärung] Kontrollieren Sie die A-, B-, C- und D-Probleme von ABC183 mit Python!

** 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

Inhaltsverzeichnis

[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)

ABC183 Zusammenfassung

Gesamtzahl der Einreichungen: 7199

Performance

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

Richtige Antwortrate nach Farbe

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 %

Kurzer Kommentar

Ein Problem (7152 Personen AC) "ReLU" Verwenden Sie die Anweisung
if, um Fälle zu trennen.
B-Problem (5919 AC) "Billard"
Sie können dies sehen, indem Sie das Verhältnis von "Geschwindigkeit in Richtung $ x $" zu "Geschwindigkeit in Richtung $ y $" berücksichtigen.
C-Problem (4633 AC) "Reisen"
Maximum $ (8-1)! = 7! = 5040 $ Probieren Sie alle Straßenbesuchsbestellungen aus. In Python können Sie mit `itertools.permutations` einfach alle Sequenzen generieren.
D Problem (3400 Personen AC) "Warmwasserbereiter" Mit der kumulativen Summe
(imos-Methode) können Sie herausfinden, wie viel heißes Wasser jedes Mal von $ O (N) $ verbraucht wird.
E Problem (1393 Personen AC) "Queen on Grid" [in diesem Artikel nicht erklärt]
Kumulative Summe DP.
F-Problem (789 Personen AC) "Confluence" [in diesem Artikel nicht erklärt] Verwenden Sie
Unionfind- und $ N $ -Zähler. Wenn Sie den kleineren Zähler zur größeren Größe der Verknüpfungskomponente hinzufügen, ist dies rechtzeitig der Fall.

Ergebnisse von mir (Unidayo) (Referenz)

screenshot.381.png

Es war ein blauer Kodierer ** für nur ** 23 Stunden.

Ein Problem "ReLU"

** 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.

Code

x = int(input())
if x >= 0:
    print(x)
else:
    print(0)

B Problem "Billard"

** 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%

Erwägung

$ G_x --S_x = T_x $, $ S_y + G_y = T_y $. Aus dem offiziellen Kommentardiagramm können Sie sich das Dreieck unten vorstellen.

abc183b.png

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.

Code

sx, sy, gx, gy = map(int, input().split())

tx = gx - sx
ty = sy + gy
dx = tx * sy / ty
print(sx + dx)

C Problem "Reisen"

** 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%

Erwägung

** * 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. ** ** **

Implementierung

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

Code

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)

D Problem "Warmwasserbereiter"

** 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%

Erwägung

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.

  • ** "$ + P_i $ von $ S_i $ bis zum Ende des Arrays" **
  • ** "$ -P_i $ von $ T_i $ bis zum Ende des Arrays" **

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.

Code

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