[PYTHON] AtCoderBeginnerContest183 Überprüfung & Zusammenfassung

AtCoder ABC183 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 183, die am 15.11.2020 (So) aufgetreten sind, beginnend mit Problem A und unter Berücksichtigung der Überlegungen. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar

Problem A ReLU

Problemstellung Die ReLU-Funktion ist wie folgt definiert. Suchen Sie mit der Ganzzahl $ x $ $ ReLU (x) $.

ReLU-Funktion mit Aktivierungsfunktion vertraut.

abc183a.py

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

B Problem Billard

Problemstellung Takahashi spielt Billard auf der Dimensionsebene $ 2 $. Die $ x $ -Achse ist eine Wand, und wenn Sie auf die Kugel treffen, springt die Kugel so, dass der Einfallswinkel und der Reflexionswinkel gleich sind. Jetzt ist Takahashis Ball in $ (S_x, S_y) $. Wenn Sie eine Kugel an einer bestimmten Koordinate treffen, rollt die Kugel linear in Richtung dieser Koordinate. Nachdem wir die Kugel genau $ 1 $ auf der $ x $ -Achse reflektiert haben, wo sollen wir auf die $ x $ -Achse zielen, um $ (G_x, G_y) $ zu passieren?

Da die Bedingung $ 0 <S_y, G_y \ leq 10 ^ 6 $ war, haben wir $ G_y $ als negativ gesetzt und als Schnittpunkt der Geradengleichung und der $ x $ -Achse gelöst.

x = S_x - S_y × (G_x - S_x) ÷ (G_y - S_y)

abc183b.py

s_x, s_y, g_x, g_y = map(int, input().split())
g_y = -g_y
print(s_x - s_y * (g_x - s_x) / (g_y - s_y))

C Problem Reisen

Problemstellung Es gibt $ N $ Städte. Es braucht $ T_ {i, j} $, um von Stadt $ i $ nach Stadt $ j $ zu gelangen. Wie viele Routen starten in der Stadt $ 1 $, besuchen alle Städte genau $ 1 $ und kehren dann in die Stadt $ 1 $ mit einer Gesamtreisezeit von nur $ K $ zurück? ??

Da die Einschränkung so klein wie $ 2 \ leq N \ leq 8 $ ist, konnte ich sie innerhalb des Ausführungszeitlimits lösen, selbst wenn ich alle durchsucht habe, aber als ich das Problem zum ersten Mal sah, $ 1 \ bis 2 \ bis 3 \ bis 4 \ bis Die 1 $ -Route und die $ 1 \ bis 4 \ bis 3 \ bis 2 \ bis 1 $ -Route haben aufgrund der Einschränkung von $ T_ {i, j} = T_ {j, i} $ dieselbe Gesamtfahrzeit. Ich dachte, ich könnte den Rechenaufwand reduzieren, wenn ich eine rekursive Funktion verwenden würde. Daher habe ich lange gebraucht, um mit dem Lösen zu beginnen.

abc183c.py

import itertools
import numpy as np
n, k = map(int, input().split())
matrix = np.zeros((n, n), dtype=int) 
for i in range(n):
    x_list = list(map(int, input().split()))
    for j in range(n):
        matrix[i, j] = x_list[j]
no_list = range(1, n)
count = 0
for temp_list in itertools.permutations(no_list):
    no = 0
    total = 0
    for next_no in temp_list:
        total += matrix[no, next_no]
        no = next_no
    total += matrix[no, 0]
    if total == k:
        count += 1
print(count)

D Problem Warmwasserbereiter

Problemstellung Es gibt einen $ 1 $ Warmwasserbereiter, der $ W $ Liter heißes Wasser pro Minute liefern kann. Es gibt $ N $ Leute. Die $ i $ -te Person plant, $ P_i $ Liter Wasser zu verwenden, das in diesem Warmwasserbereiter von $ S_i $ bis $ T_i $ gekocht wird (außer nur $ T_i $). Das heiße Wasser kühlt schnell ab und kann nicht gespeichert werden. Ist es möglich, alle wie geplant mit heißem Wasser zu versorgen?

Aus irgendeinem Grund habe ich es während des Wettbewerbs mit Dikt gelöst, aber ich kann es auch mit Liste lösen. Erstens ist es verschwenderisch und bedauerlich, weil es nicht notwendig ist, durch Erhöhen und Verringern getrennt zu verwalten.

abc183d.py

n, w = map(int, input().split())
start_dict = {}
end_dict = {}
for i in range(n):
    s, t, p = map(int, input().split())
    if s in start_dict:
        start_dict[s] += p
    else:
        start_dict[s] = p
    if t in end_dict:
        end_dict[t] += p
    else:
        end_dict[t] = p
now = 0
flag = 1
for i in range(2 * 100000):
    if i in start_dict:
        now += start_dict[i]
    if i in end_dict:
        now -= end_dict[i]
    if now > w:
        flag = 0
        break
if flag == 1:
    print("Yes")
else:
    print("No")

Code geändert unter Bezugnahme auf die Erklärung.

abc183d.py

n, w = map(int, input().split())
a_list = [0] * 200001
for i in range(n):
    s, t, p = map(int, input().split())
    a_list[s] += p
    a_list[t] -= p
for i in range(1, 200001):
    a_list[i] += a_list[i - 1]
if max(a_list) > w:
    print("No")
else:
    print("Yes")

Das E-Problem endete, ohne aus 'TLE' herauszukommen. Ich möchte es hinzufügen, wenn ich Zeit habe.

Vielen Dank für das Lesen bis zum Ende.