AtCoder ABC166 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 166, die am 03.05.2020 (So) aufgetreten sind, beginnend mit Problem A und unter Berücksichtigung der Überlegungen. Das erste Halbjahr befasst sich mit Fragen bis ABC. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF
Problemstellung AtCoder veranstaltet jeden Samstag einen Wettbewerb. Es gibt zwei Arten von Wettbewerben, ABC und ARC, für $ 2 $, von denen einer jede Woche stattfindet. Das ARC findet eine Woche nach dem ABC statt, und das ABC findet eine Woche nach dem ARC statt. Sie erhalten die Zeichenfolge $ S $, die den Wettbewerb darstellt, der letzte Woche stattgefunden hat. Geben Sie daher die Zeichenfolge aus, die den Wettbewerb darstellt, der diese Woche stattgefunden hat.
Ich denke, dass dieser Bereich ohne besondere Probleme gelöst werden kann. Wenn die if-Anweisung bestimmt, ob die empfangene Zeichenfolge ABC oder ARC ist, ist der Vorgang abgeschlossen.
abc166a.py
s = input()
if s == "ABC":
print("ARC")
else:
print("ABC")
Problemstellung In einer Stadt leben $ N $ Menschen (Sunuke $ 1 $, Sunuke $ 2 $, ..., Sunuke $ N $). $ K $ Arten von Süßigkeiten ($ 1 $ Süßigkeiten, $ 2 $ Süßigkeiten, ...., $ K $ Süßigkeiten) werden in dieser Stadt angeboten. Die Person, die die Süßigkeiten $ i $ besitzt, ist Sunuke-kun $ A_ {i, 1}, A_ {i, 2}, ⋯, A_ {i, d_i} $, insgesamt $ d_i $ Personen. Takahashi wird nun durch die Stadt reisen und mit Sunuke spielen, der keine $ 1 $ Süßigkeiten hat. Wie viele Sunuke-Kun werden zu diesem Zeitpunkt schelmisch sein?
Machen Sie eine Liste "kun_list", um Mr. Sunuke aufzunehmen, der schelmisch sein wird. Wenn Sie die Süßigkeiten nicht zuerst informieren, wird nicht jeder die Süßigkeiten haben und Sie werden boshaft sein. Wenn Sie also die dort angegebenen Süßigkeiteninformationen verwenden, um Sunuke, der Süßigkeiten hat, von der Unfug-Liste zu entfernen, erhalten Sie Sunuke, der keine Süßigkeiten hat und schelmisch ist. Es bleibt auf der Liste und kann durch Zählen der Anzahl der Personen gelöst werden.
abc166b.py
n, k = map(int, input().split())
kun_list = [1] * n
for i in range(0, k):
d = int(input())
a_list = list(map(int, input().split()))
for a in a_list:
kun_list[a-1] = 0
print(sum(kun_list))
Problemstellung Auf den AtCoder-Hügeln gibt es $ N $ Observatorien, und die Höhe des Observatoriums $ i $ beträgt $ H_i $. Es gibt auch eine $ M $ Buchstraße, die verschiedene Observatorien verbindet, und die Straße $ j $ verbindet das Observatorium $ A_j $ und das Observatorium $ B_j $. Observatorium $ i $ ist ein gutes Observatorium bedeutet, dass das Observatorium $ i $ höher ist als jedes Observatorium, das vom Observatorium $ i $ über eine einzige Straße erreicht werden kann. .. Selbst wenn es kein Observatorium gibt, das vom Observatorium $ i $ über eine einzige Straße erreicht werden kann, wird das Observatorium $ i $ als gutes Observatorium bezeichnet. Finden Sie heraus, wie viele gute Observatorien es gibt.
Finden Sie in der Erklärung die maximale Höhe $ maxH_i $ des (benachbarten) Observatoriums, die über eine Straße vom Observatorium $ i $ an jedem Observatorium erreicht werden kann, und verwenden Sie ein gutes Observatorium, wenn $ H_i> maxH_i $. Aus diesem Grund habe ich die Nummer gezählt. Ich habe vorerst eine Liste von Observatorien mit dem Namen "ten_list" als gute Observatorien erstellt. Bei einer Straßeninformation sind eines oder beide Observatorien keine guten Observatorien mehr. Daher haben wir die Höhen verglichen und die "ten_list" (beide Observatorien) aktualisiert Es ist kein gutes Observatorium, wenn die Höhen gleich sind. Zählen Sie abschließend die Anzahl der verbleibenden guten Observatorien.
abc166c.py
n, m = map(int, input().split())
h_list = list(map(int, input().split()))
ten_list = [1] * n
for i in range(0, m):
a, b = map(int, input().split())
if h_list[a - 1] <= h_list[b - 1]:
ten_list[a - 1] = 0
if h_list[a - 1] >= h_list[b - 1]:
ten_list[b - 1] = 0
print(sum(ten_list))
Dies ist das Ende der ersten Hälfte. In der zweiten Hälfte wird das DEF-Problem erläutert. Ich war zum Zeitpunkt des Wettbewerbs ein wenig besorgt, weil das C-Problem ein Problem war, das fast genauso gelöst werden konnte wie das B-Problem, aber ich konnte es bisher lösen, ohne stecken zu bleiben. Nachdem ich ABC auch in diesem Wettbewerb gelöst hatte, blieb ich stecken und versuchte und irrte, aber am Ende endete es ohne Ausgabe von "AC", und ich bedauere, dass es mit der Geschwindigkeit des Kurzstreckenlaufs zum C-Problem verglichen wurde. .. Es war ungefähr 14 Minuten nach dem Beginn des C-Problems. Schließlich möchte ich aus dem Rennen aussteigen, indem ich nach einem schwierigen Problem frage. Vielen Dank, dass Sie vorerst bis zum Ende der ersten Hälfte gelesen haben. Fortsetzung in der zweiten Hälfte.
Recommended Posts