[PYTHON] AtCoderBeginnerContest168 Review & Summary (zweite Hälfte)

AtCoder ABC168 Dies ist eine Zusammenfassung der Probleme des AtCoder-Anfängerwettbewerbs 168, der am 17.05.2020 (So) in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung stattfand. Die zweite Hälfte befasst sich mit dem DEF-Problem. Klicken Sie hier für die erste Hälfte. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF

D Problem .. (Doppelpunkte)

Problemstellung An einem Ort gibt es eine Höhle. Die Höhle hat $ N $ Zimmer und $ M $ Buchgänge, wobei die Zimmer von $ 1 $ bis $ N $ und die Gänge von $ 1 $ bis $ M $ nummeriert sind. Passage $ i $ verbindet Raum $ A_i $ und Raum $ B_i $ in beide Richtungen. Jedes $ 2 $ Zimmer kann über mehrere Gänge erreicht werden. Zimmer $ 1 $ ist ein spezielles Zimmer mit Höhleneingang. Das Innere der Höhle ist dunkel, deshalb habe ich beschlossen, in jedem Raum einen $ 1 $ Führer einzurichten, mit Ausnahme des Raumes $ 1 $. Der Pfad für jeden Raum sollte auf $ 1 $ des Raums zeigen, der durch den Gang direkt mit diesem Raum verbunden ist. Da das Innere der Höhle gefährlich ist, besteht das Ziel darin, die folgenden Bedingungen für alle Räume außer Raum $ 1 $ zu erfüllen. Wenn Sie von diesem Raum aus beginnen und wiederholen: "Sehen Sie sich den Pfad in dem Raum an, in dem Sie sich befinden, und gehen Sie zu dem Raum, auf den er zeigt", erreichen Sie Raum $ 1 $ mit der geringsten Anzahl von Zügen. Stellen Sie fest, ob es Placements gibt, mit denen Sie Ihre Ziele erreichen können, und drucken Sie in diesem Fall $ 1 $ für solche Placements. Ausgabe Wenn es keine Richtlinienanordnung gibt, mit der das Ziel erreicht werden kann, geben Sie "Nein" aus. Wenn vorhanden, drucken Sie die Zeile $ N $. Geben Sie "Ja" in die Zeile $ 1 $ und die Zimmernummer ein, auf die der Raum $ i $ in der Zeile $ i (2 \ leq i \ leq N) $ zeigt.

Das Problem war vorerst leicht zu verstehen, daher habe ich es gelöst, sobald ich es implementiert hatte. Ich dachte, dass es einen absoluten Weg gibt, um das Ziel zu erreichen, also habe ich keine Beschreibung für die Ausgabe von "Nein" geschrieben (ich konnte sie nicht schreiben, weil mir überhaupt kein Beispiel für "Nein" einfiel). Betrachten Sie einfach ein geeignetes Eingabebeispiel.

Lassen Sie uns zunächst den mit Raum 1 verbundenen Raum überprüfen. Die mit diesen Räumen 1 verbundenen Räume 8, 9 und 15 gelten als Räume mit einer Tiefe von 1.

Als nächstes überprüfen wir den Raum, der zuvor rot gestrichen wurde. Die mit diesen Räumen verbundenen Räume 4, 5, 6 und 12 gelten als Räume mit einer Tiefe von 2.

Überprüfen wir auch den Raum, der zuvor rot gestrichen wurde. Die mit diesen Räumen verbundenen Räume 7, 10 und 11 gelten als Räume mit einer Tiefe von 3.

Es wiederholt sich nur. Wir werden die zuvor rot gestrichenen Räume überprüfen und die mit diesen Räumen verbundenen Räume 2 und 3 als Räume mit einer Tiefe von 4 betrachten.

Stellen Sie sich die Räume 13 und 14 als Räume mit einer Tiefe von 5 vor.

Stellen Sie sich Raum 16 als einen Raum mit einer Tiefe von 6 vor.

Dies ist das Ende der Suche. Wenn Sie danach einen flachen Raum aus dem tiefsten Raum auswählen, ist dies der kürzeste Weg von diesem Raum zu Raum 1.

In der tatsächlichen Implementierung wird die Antwort für jeden Raum in der Phase des Malens aufgezeichnet. Um dieses Problem zu lösen, werden Informationen darüber, welcher Raum mit jedem Raum verbunden ist, als Datenstruktur gespeichert. Lassen Sie uns zunächst den mit Raum 1 verbundenen Raum überprüfen.

Schreiben Sie "1" als Leitfaden für die Räume 8, 9 und 15, die mit diesen Räumen 1 verbunden sind.

Schauen wir uns als nächstes die Räume 8, 9 und 15 mit den Verkehrsschildern an. Lassen Sie uns zunächst den mit Raum 8 verbundenen Raum überprüfen.

Ignorieren Sie die bereits roten Räume und schreiben Sie "8" als Leitfaden für die noch hellblauen Räume 5 und 6. Dies kann in kürzester Entfernung zu Raum 1 zurückgebracht werden, indem Raum 6 → Raum 8 → Raum 1 befolgt wird (dasselbe gilt für Raum 5).

Als nächstes überprüfen wir den Raum, der mit Raum 9 verbunden ist.

Ignorieren Sie hier nach wie vor den Raum, der bereits rot ist, und geben Sie "9" als Leitfaden für Raum 4 ein, der noch hellblau ist. Sie können in kürzester Entfernung zu Raum 1 zurückkehren, indem Sie Raum 4 → Raum 9 → Raum 1 folgen. Raum 5 ist bereits rot und kann ignoriert werden, da es auf einer anderen Route einen kürzesten Weg zurück zu Raum 1 gibt.

Durch Bestätigen und Ausfüllen der Richtlinie auf diese Weise ist es möglich, eine Antwort zu geben.

abc168d.py

n, m = map(int, input().split())
dict_road = {}
dict_room = {}
for i in  range(0, m):
    a, b = map(int, input().split())
    if a in dict_road:
        dict_road[a].append(b)
    else:
        dict_road[a] = [b]
    if b in dict_road:
        dict_road[b].append(a)
    else:
        dict_road[b] = [a]
start_list = dict_road[1]
temp_list = []
for no in start_list:
    dict_room[no] = 1
    temp_list.append(no)
while True:
    next_temp_list = []
    for no in temp_list:
        for next_no in dict_road[no]:
            if next_no not in dict_room:
                dict_room[next_no] = no
                next_temp_list.append(next_no)
    if len(next_temp_list) == 0:
        break
    temp_list = next_temp_list
print("Yes")
for i in range(2, n + 1):
    print(dict_room[i])

E Problem ∙ (Aufzählungszeichen)

Problemstellung Ich habe $ N $ Sardinen gefangen. Die Köstlichkeit der $ i $ Sardine ist $ A_i $ und das Aroma ist $ B_i $. Wählen Sie $ 1 $ oder mehr Sardinen aus dieser Liste aus und legen Sie sie in dieselbe Kühlbox. Sie können jedoch nicht $ 2 $ Tiere auswählen, die nicht gleichzeitig nahe beieinander liegen. $ i $ und $ j (\ neq i) $ $ squid sind nicht gut miteinander verbunden, wenn (und nur) $ A_i⋅A_j + B_i⋅B_j = 0 $. Wie viele Möglichkeiten gibt es, Sardinen zu wählen? Die Antwort kann sehr groß sein. Drucken Sie den Rest geteilt durch $ 1000000007 $ aus.

Ich wollte das E-Problem lösen, weil ich das D-Problem ziemlich früh bestehen konnte, aber ich konnte es doch nicht lösen. Es war Zeit, eine Kombination aus zwei Sardinen zu finden, mit denen ich nicht klar kam.

F Problem Drei Variablen Spiel

Problemstellung Es gibt eine endlose Wiese. Auf dieser Wiese gibt es $ 1 $ Kopfkühe, die vernachlässigbar klein sind. Der Punkt, an dem die Kuh um $ x \ \ mathrm {cm} $ nach Süden und um $ y \ \ mathrm {cm} $ nach Osten bewegt wird, wird als $ (x, y) $ ausgedrückt. Der Punkt, an dem sich die Kuh selbst befindet, ist $ (0,0) $. Zusätzlich werden $ N $ vertikale Linien und $ M $ horizontale Linien auf der Wiese gezeichnet. $ i $ Die vertikale Linie ist die Linie, die den Punkt $ (A_i, C_i) $ und den Punkt $ (B_i, C_i) $ verbindet, und die horizontale Linie $ j $ ist der Punkt $ (D_j, E_j) $ und der Punkt $. (D_j, F_j) Eine Linie, die $ verbindet. In welchem Bereich kann sich die Kuh bewegen, wenn sich die Kuh frei bewegen kann, solange sie die Linie (einschließlich der Endpunkte) nicht überschreitet? $ \ Mathrm {cm ^ 2} $. Wenn der Bereich dieses Bereichs unendlich ist, geben Sie stattdessen "INF" aus.

Wird der Tag kommen, an dem dieser Bereich gelöst werden kann?

Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.