AtCoder ABC170 This is a summary of the problems of AtCoder Beginner Contest 170, which was held on 2020-06-14 (Sun), in order from problem A, taking into consideration the consideration. The first half deals with problems up to ABCD. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF
Problem statement $ 5 $ There are two variables $ x_1, x_2, x_3, x_4, x_5 $. Initially, the variable $ x_i $ was assigned the integer $ i $. Sunuke-kun chose $ 1 $ from these variables and assigned $ 0 $ to that variable. Given the values of $ 5 $ variables after Sunuke-kun did this. Please answer which variable Sunuke-kun assigned $ 0 $ to.
For submission, the for statement is turned so that the part where the element is 0 is output. Most programming languages start with $ 0 $ in the array, so if you pay attention to that, you shouldn't have to worry about WA.
abc170a.py
x = list(map(int, input().split()))
for i in range(5):
if x[i] == 0:
print(i + 1)
After looking at the explanation after finishing, I thought that the answer would be $ 15 − x_1 − x_2 − x_3 − x_4 − x_5 $.
Problem statement There are some animals in the garden. These are either cranes with $ 2 $ legs or turtles with $ 4 $ legs, respectively. Takahashi says, "The total number of animals in the garden is $ X $, and the total number of their paws is $ Y $." Determine if there is a combination of crane and turtle numbers that makes this statement correct.
I added the rules with if statements in the order I thought.
abc170b.py
x, y = map(int, input().split())
if y < 2 * x or x * 4 < y:
print("No")
else:
if y % 2 == 1:
print("No")
else:
print("Yes")
Problem statement Given the integer $ X $ and the integer sequence $ p_1,…, p_N $ of length $ N $. Find the integer (not necessarily positive) that is not included in the integer sequence $ p_1,…, p_N $ that is closest to $ X $, that is, the one with the smallest absolute difference from $ X $. .. If there are multiple such integers, please answer the smallest one.
The numbers not included in the integer sequence were searched in order from the input $ X $. If $ N $ is large, ```if x in list:` `` will take a lot of time, so I change list to dict, but this time $ N $ is small, so I left it as it is.
For example, if the input is $ 6 $, the search is performed in the order of 6, 5, 7, 4, 8, .... (The program checks the input $ x = 6 ± 0 $ twice, but I thought that there would be no big difference in execution time, so I implemented it in a form that is easy to implement.)
abc170c.py
x, n = map(int, input().split())
p_list = list(map(int, input().split()))
for i in range(0, n // 2 + 2):
if x - i not in p_list:
print(x - i)
break
if x + i not in p_list:
print(x + i)
break
Problem statement Given a sequence $ A $ of length $ N $. Answer the number of integers $ i (1 \ leq i \ leq N) $ that satisfy the following properties. ・ For any integer $ j (1 \ leq j \ leq N) $ that is $ i \ neq j $, $ A_i $ is not divisible by $ A_j $
I thought about various ideas during the contest, but I couldn't solve it. I submitted the following code for "TLE".
abc170dTLE.py
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
flag_list = [1] * len(sorted_dict)
i = 0
for key, count in sorted_dict:
if flag_list[i] == 0:
i += 1
continue
if count > 1:
flag_list[i] = 0
i += 1
j = i
for key1, count1 in sorted_dict[i:]:
if flag_list[j] == 0:
j += 1
continue
if key1 % key == 0:
flag_list[j] = 0
j += 1
print(sum(flag_list))
I thought that the amount of calculation in the latter half could be reduced by sorting and seeing if the smaller ones could break the larger ones, but that was no good.
Actually, it is managed by putting it in a set, and $ 2 $ times, $ 3 $ times, $ 4 $ times, ..., $ k $ times ($ k $ is $ a_i × k \ leq a_ {max) It seems that it can be solved by removing the largest integer $ k $) that satisfies} $ from the set. I couldn't think of it.
abc170d.py
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
a_set = set(a_list)
m = max(a_list)
for key, count in sorted_dict:
if key in a_set:
j = key * 2
while j <= m:
a_set.discard(j)
j += key
if count > 1:
a_set.discard(key)
print(len(a_set))
This is the end of the first half. Personally, I've been dropping rates lately, but it's natural because I can't secure time to solve past questions in data analysis competitions or writing papers. I have a lot of study for the competition, so I would like to digest it little by little (I want to understand and implement the minimum methodology by the next competition). For the time being, at the very least, I would like to aim for ABC to maintain the habit of participating every time for a while. Thank you for reading to the end of the first half.
The second half will explain the EF problem, but I don't think I can write an article in time (sweat).
Recommended Posts