[PYTHON] AtCoderBeginnerContest168 Review & Summary (second half)

AtCoder ABC168 This is a summary of the AtCoder Beginner Contest 168 questions that were held on 2020-05-17 (Sun), starting with question A and taking into consideration the considerations. The second half deals with the DEF problem. Click here for the first half. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

D problem .. (Double Dots)

Problem statement There is a cave somewhere. The cave has $ N $ rooms and $ M $ book walkways, with rooms numbered from $ 1 $ to $ N $ and walkways numbered from $ 1 $ to $ M $. The passage $ i $ connects room $ A_i $ and room $ B_i $ in both directions. Every $ 2 $ room can be reached through several aisles. Room $ 1 $ is a special room with a cave entrance. The inside of the cave is dim, so I decided to set up a $ 1 $ guide in each room except the room $ 1 $. The trail for each room should point to $ 1 $ for the room that is directly connected to that room by the aisle. Since the inside of the cave is dangerous, the goal is to meet the following conditions for all rooms except room $ 1 $. If you start from that room and repeat "look at the path in the room you are in and move to the room it points to", you will reach room $ 1 $ with the least number of moves. Determine if there are any placements that can reach your goal, and if so, print $ 1 $ for such placements. Output If there is no guideline arrangement that can achieve the goal, output "No". If it exists, print the $ N $ line. Print "Yes" on the $ 1 $ line and the room number pointed to by the room $ i $ on the $ i (2 \ leq i \ leq N) $ line.

For the time being, the problem was easy to understand, so I implemented it and solved it. I thought that there was an absolute way to achieve the goal, so I didn't write a description to output "No" (I couldn't write it because I couldn't think of an example of "No" in the first place). Simply consider an appropriate input example.

First, let's check the room connected to room 1. Rooms 8, 9 and 15 connected to these rooms 1 are considered to be rooms with a depth of 1.

Next, let's check the room that was painted red earlier. Rooms 4, 5, 6 and 12 connected to these rooms are considered to be rooms with a depth of 2.

Similarly, let's check the room that was painted red earlier. Rooms 7, 10 and 11 connected to these rooms are considered to be rooms with a depth of 3.

It's just repeating. Check the rooms that have been painted red earlier, and consider the rooms 2 and 3 connected to these rooms to be rooms with a depth of 4.

Think of rooms 13 and 14 as rooms with a depth of 5.

Think of room 16 as a room with a depth of 6.

This is the end of the search. After that, if you select one shallow room from the deepest room, it will be the shortest route from that room to room 1.

In the actual implementation, the answer is recorded for each room at the stage of painting. In order to solve this problem, information on which room is connected to each room is stored as a data structure. First, let's check the room connected to room 1.

Write "1" as a guide to rooms 8, 9 and 15 that are connected to these rooms 1.

Next, let's take a look at rooms 8, 9 and 15 with the road signs in order. First, let's check the room connected to room 8.

Ignore the rooms that are already red, and write "8" as a guide to rooms 5 and 6 that are still light blue. This can be returned to Room 1 in the shortest distance by following Room 6 → Room 8 → Room 1 (same for Room 5).

Next, check the room connected to room 9.

Ignore the room that is already red as before, and write "9" as a guide to room 4 that is still light blue. This can be returned to Room 1 in the shortest distance by following Room 4 → Room 9 → Room 1. Room 5 is already red and can be ignored as there is a shortest route back to room 1 on another route.

By confirming and filling in the guideline like this, it is possible to make an answer.

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 ∙ (Bullet)

Problem statement I caught $ N $ sardines. The deliciousness of the $ i $ sardine is $ A_i $ and the aroma is $ B_i $. Select $ 1 $ or more of sardines and put them in the same cooler box, but you cannot select $ 2 $ sardines that are not close to each other at the same time. The $ i $ and $ j (\ neq i) $ sardines are not on good terms when (and only) $ A_i⋅A_j + B_i⋅B_j = 0 $. How many ways to choose sardines? The answer can be very large, so print out the remainder divided by $ 1000000007 $.

I wanted to solve the E problem because I was able to pass the D problem at a fairly early stage, but I couldn't solve it after all. It was time over to find a combination of two sardines that I didn't get along with.

F problem Three Variables Game

Problem statement There is an endless meadow. There are $ 1 $ head cows on this grassland that are negligibly small in size. The point moved to the south by $ x \ \ mathrm {cm} $ and to the east by $ y \ \ mathrm {cm} $ is expressed as $ (x, y) $. The point where the cow itself is is $ (0,0) $. In addition, $ N $ vertical lines and $ M $ horizontal lines are drawn on the grasslands. $ i $ The vertical line is the line segment connecting the point $ (A_i, C_i) $ and the point $ (B_i, C_i) $, and the $ j $ horizontal line is the point $ (D_j, E_j) $ and the point $. (D_j, F_j) A line segment connecting $. When the cow can move around freely as long as it does not pass through the line segment (including the endpoints), what is the area of the range in which the cow can move around $ \ mathrm {cm ^ 2} $? If the area of this range is infinite, output "INF" instead.

Will the day when this area can be solved come?

Thank you for reading the second half to the end.