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