[PYTHON] AtCoderBeginnerContest168 Review & Summary (second semestre)

AtCoder ABC168 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 168 qui s'est tenu le 17/05/2020 (dimanche) dans l'ordre du problème A, en tenant compte de la considération. La seconde moitié traite du problème DEF. Cliquez ici pour la première moitié. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF

Problème D .. (Double Dots)

Énoncé du problème Il y a une grotte en un seul endroit. La grotte a des chambres $ N $ et des passages de livres $ M $, les salles sont numérotées de 1 $ à $ N $ et les passages sont numérotés de 1 $ à $ M $. Le passage $ i $ relie la salle $ A_i $ et la salle $ B_i $ dans les deux sens. Chaque chambre à 2 $ est accessible par plusieurs allées. La chambre 1 $ est une chambre spéciale avec une entrée dans la grotte. L'intérieur de la grotte est sombre, j'ai donc décidé de mettre en place un guide à 1 $ dans chaque pièce sauf la chambre à 1 $. Le sentier de chaque pièce doit indiquer 1 $ de la pièce directement reliée à cette pièce par l'allée. L'intérieur de la grotte étant dangereux, le but est de respecter les conditions suivantes pour toutes les pièces sauf la chambre 1 $. Si vous partez de cette pièce et répétez "regardez le panneau de signalisation dans la pièce dans laquelle vous vous trouvez et allez dans la pièce vers laquelle il pointe", vous atteindrez la salle $ 1 $ avec le nombre minimum de coups. Déterminez s'il existe des emplacements qui peuvent vous aider à atteindre vos objectifs et, le cas échéant, imprimez 1 $ pour ces emplacements. Sortie S'il n'y a pas d'arrangement de lignes directrices permettant d'atteindre l'objectif, indiquez «Non». Sortie de la ligne $ N $ si elle existe. Imprimez "Oui" sur la ligne $ 1 $ et le numéro de la chambre pointé par la pièce $ i $ sur la ligne $ i (2 \ leq i \ leq N) $.

Pour le moment, le problème était facile à comprendre, donc je l'ai résolu une fois que je l'ai implémenté. Je pensais qu'il y avait un moyen absolu d'atteindre l'objectif, donc je n'ai pas écrit de description pour afficher "Non" (je ne pouvais pas l'écrire parce que je ne pouvais pas penser à un exemple de "Non" en premier lieu). Considérez simplement un exemple d'entrée approprié.

Commençons par vérifier la pièce connectée à la pièce 1. Les pièces 8, 9 et 15 reliées à ces pièces 1 sont considérées comme des pièces d'une profondeur de 1.

Ensuite, vérifions la pièce qui a été peinte en rouge plus tôt. Les pièces 4, 5, 6 et 12 reliées à ces pièces sont considérées comme des pièces d'une profondeur de 2.

De même, vérifions la pièce peinte en rouge plus tôt. Les pièces 7, 10 et 11 reliées à ces pièces sont considérées comme des pièces d'une profondeur de 3.

C'est juste répéter. Nous vérifierons les pièces qui ont été peintes en rouge précédemment et considérerons les pièces 2 et 3 reliées à ces pièces comme des pièces d'une profondeur de 4.

Considérez les pièces 13 et 14 comme des pièces d'une profondeur de 5.

Considérez la pièce 16 comme une pièce d'une profondeur de 6.

C'est la fin de la recherche. Après cela, si vous sélectionnez une pièce peu profonde de la pièce la plus profonde, ce sera le chemin le plus court de cette pièce à la pièce 1.

Dans la mise en œuvre réelle, la réponse est enregistrée pour chaque pièce au stade de la peinture. Afin de résoudre ce problème, les informations sur la pièce connectée à chaque pièce sont stockées sous forme de structure de données. Commençons par vérifier la pièce connectée à la pièce 1.

Écrivez «1» comme guide des salles 8, 9 et 15 qui sont reliées à ces pièces 1.

Ensuite, jetons un œil aux salles 8, 9 et 15 avec les panneaux de signalisation dans l'ordre. Commençons par vérifier la pièce connectée à la pièce 8.

Ignorez les pièces qui sont déjà rouges et écrivez «8» comme guide pour les salles 5 et 6 qui sont encore bleu clair. Cela peut être retourné à la salle 1 dans la distance la plus courte en suivant la salle 6 → la salle 8 → la salle 1 (même chose pour la salle 5).

Ensuite, vérifions la pièce connectée à la pièce 9.

Ici, comme auparavant, ignorez la pièce qui est déjà rouge et entrez «9» comme guide pour la pièce 4 qui est encore bleu clair. Vous pouvez revenir à la salle 1 dans la distance la plus courte en suivant la salle 4 → la pièce 9 → la pièce 1. La salle 5 est déjà rouge et peut être ignorée car il existe un chemin le plus court pour retourner à la salle 1 sur un autre itinéraire.

En confirmant et en remplissant la directive comme celle-ci, il est possible de répondre.

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

Problème E ∙ (Bullet)

Énoncé du problème J'ai attrapé des sardines $ N $. Le caractère délicieux de la sardine $ i $ est $ A_i $ et l'arôme est $ B_i $. Sélectionnez 1 $ ou plus de sardines dans cette liste et placez-les dans la même glacière, mais vous ne pouvez pas sélectionner des animaux à 2 $ qui ne sont pas proches les uns des autres en même temps. Les squids $ i $ et $ j (\ neq i) $ $ ne sont pas en bons termes quand (et seulement) $ A_i⋅A_j + B_i⋅B_j = 0 $. Combien de façons de choisir les sardines? La réponse peut être très volumineuse, alors imprimez le reste divisé par 1000000007 $.

Je voulais résoudre le problème E parce que j'étais capable de passer le problème D assez tôt, mais je ne pouvais pas le résoudre après tout. Il était temps de trouver une combinaison de deux sardines avec lesquelles je ne m'entendais pas.

Problème F Jeu des trois variables

Énoncé du problème Il y a une prairie sans fin. Il y a des vaches de tête à 1 $ sur cette prairie dont la taille est négligeable. Le point où la vache est déplacée vers le sud de $ x \ \ mathrm {cm} $ et vers l'est par $ y \ \ mathrm {cm} $ est exprimé par $ (x, y) $. Le point où se trouve la vache elle-même est $ (0,0) $. De plus, des lignes verticales $ N $ et des lignes horizontales $ M $ sont dessinées sur le pré. $ i $ La ligne verticale relie le point $ (A_i, C_i) $ et le point $ (B_i, C_i) $, et la ligne horizontale $ j $ relie le point $ (D_j, E_j) $ et le point $ (D_j, F_j) Une ligne reliant $. Quelle est la superficie de la capacité de la vache à se déplacer lorsqu'elle est libre de se déplacer tant qu'elle ne franchit pas la ligne (y compris les extrémités)? $ \ Mathrm {cm ^ 2} $. Si la zone de cette plage est infinie, indiquez "INF" à la place.

Le jour où ce domaine pourra être résolu viendra-t-il?

Merci d'avoir lu la seconde moitié jusqu'à la fin.