AtCoderBeginnerContest166 Review & Summary (first half)

AtCoder ABC166 This is a summary of the AtCoder Beginner Contest 166 problems that took place on 2020-05-03 (Sun), starting with problem A and taking into account the considerations. The first half deals with problems up to ABC. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

Problem A Registration

Problem statement AtCoder holds a contest every Saturday. There are two types of contests, ABC and ARC, for $ 2 $, one of which is held weekly. The ARC will be held the week after the ABC, and the ABC will be held the week after the ARC. You will be given the string $ S $ that represents the contest that was held last week, so please output the string that represents the contest that was held this week.

I think that this area can be solved without any particular trouble. If the if statement determines whether the received character string is ABC or ARC, the process is complete.

abc166a.py


s = input()
if s == "ABC":
    print("ARC")
else:
    print("ABC")

Problem B Trick or Treat

Problem statement There are $ N $ people living in a city (Sunuke $ 1 $, Sunuke $ 2 $, ..., Sunuke $ N $). The city sells $ K $ types of sweets ($ 1 $ sweets, $ 2 $ sweets, ...., $ K $ sweets). The person who owns the sweets $ i $ is Sunuke-kun $ A_ {i, 1}, A_ {i, 2}, ⋯, A_ {i, d_i} $, a total of $ d_i $ people. Takahashi is now going around the city and pranking Sunuke, who doesn't have $ 1 $ in sweets. How many Sunuke-kun will be mischievous at this time?

Make a list kun_list to record the mischievous Mr. Sunuke. If you don't give the sweets information first, everyone will not have the sweets and you will be mischievous. So, if you use the sweets information given there to remove Sunuke who has sweets from the mischievous list, you will end up with Sunuke who does not have sweets and is mischievous. It will remain on the list and can be solved by counting the number of people.

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

C problem Peaks

Problem statement There are $ N $ observatories on the AtCoder hills, and the observatory $ i $ is at an altitude of $ H_i $. There is also a $ M $ book road connecting different observatories, and the road $ j $ connects the observatory $ A_j $ and the observatory $ B_j $. Observatory $ i $ is a good observatory means that the observatory $ i $ is higher than any observatory that can be reached from the observatory $ i $ using a single road. .. Even if there is no observatory that can be reached from the observatory $ i $ using a single road, the observatory $ i $ is said to be a good observatory. Find out how many good observatories there are.

In the explanation, find the maximum height $ maxH_i $ of the (adjacent) observatory that can be reached by one road from the observatory $ i $ at each observatory, and if $ H_i> maxH_i $, use a good observatory. Because of that, I used to count the number. I made a list of observatories called ten_list as a good observatory for the time being. Given one road information, either or both observatories will no longer be good observatories, so we compared the heights and updated the ten_list (both observatories It is not a good observatory when the heights are equal). Finally, count the number of good observatories left.

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

This is the end of the first half. The second half will explain the DEF problem. I was a little worried at the time of the contest because the C problem was a problem that could be solved in almost the same way as the B problem, but I was able to solve it so far without getting stuck. However, after solving ABC in this contest as well, I got stuck and tried and errored, but in the end I couldn't get "AC", and I regret that it was compared to the speed of sprinting up to the C problem. .. It was about 14 minutes after the start that I passed the C problem. After all, I want to get out of the foot race by asking about one difficult problem. Thank you for reading to the end of the first half for the time being. Continued in the second half.

Recommended Posts

AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest169 Review & Summary (first half)
AtCoderBeginnerContest174 Review & Summary (first half)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (first half)
AtCoderBeginnerContest170 Review & Summary (first half)
AtCoderBeginnerContest167 Review & Summary (first half)
AtCoderBeginnerContest177 Review & Summary (first half)
AtCoderBeginnerContest168 Review & Summary (first half)
AtCoderBeginnerContest178 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (first half)
AtCoderBeginnerContest161 Review & Summary (first half)
AtCoderBeginnerContest172 Review & Summary (first half)
AtCoderBeginnerContest176 Review & Summary (first half)
AtCoderBeginnerContest178 Review & Summary (second half)
AtCoderBeginnerContest161 Review & Summary (second half)
AtCoderBeginnerContest164 Review & Summary (second half)
AtCoderBeginnerContest176 Review & Summary (second half)
AtCoderBeginnerContest168 Review & Summary (second half)
AtCoderBeginnerContest169 Review & Summary (second half)
AtCoderBeginnerContest166 Review & Summary (second half)
AtCoderBeginnerContest171 Review & Summary (second half)
AtCoderBeginnerContest174 Review & Summary (second half)
AtCoderBeginnerContest173 Review & Summary (second half)
AtCoderBeginnerContest177 Review & Summary (second half)
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest179 Review & Summary
Django Girls Tutorial Summary First Half
AtCoder Review of past questions (first half of 12 / 8,9)