AtCoder ABC171 This is a summary of the problems of AtCoder Beginner Contest 171 held on 2020-06-21 (Sun) in order from problem A, taking into consideration the consideration. The second half deals with the DE 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
Problem statement You have a sequence $ A $ consisting of $ N $ positive integers $ A_1, A_2, ⋯, A_N $. You will continue to do the following $ Q $ times. ・ In the $ i $ operation, all elements with the value $ B_i $ are replaced with $ C_i $. For all $ i (1 \ leq i \ leq Q) $, find the sum of all the elements of the sequence $ A $ after the $ i $ operation, $ S_i $.
I thought that I would run out of time if I calculated the sum every time, so I decided to calculate the difference for each operation. The sequence $ A $ is managed by dict.
abc171d.py
n = int(input())
a_list = list(map(int, input().split()))
a_dict = {}
total = 0
for a in a_list:
if a in a_dict:
a_dict[a] += 1
else:
a_dict[a] = 1
total += a
q = int(input())
for i in range(q):
b, c = map(int, input().split())
if b in a_dict:
if c in a_dict:
a_dict[c] += a_dict[b]
else:
a_dict[c] = a_dict[b]
total -= a_dict[b] * b
total += a_dict[b] * c
a_dict[b] = 0
print(total)
I was able to solve the D problem smoothly. However, I couldn't solve the next E problem.
Problem statement There are $ N $ (** even **) cats. Each Sunuke-kun is numbered $ 1,2,…, N $. Each Sunuke-kun has a red scarf around his neck, and the scarf has $ 1 $ of the non-negative integer that he likes best. Sunuke and his colleagues recently learned an operation called xor (exclusive OR) for integers. Immediately, Sunuke-kun and others who wanted to use this operation decided to calculate the integer xor written on the scarf of Sunuke-kun other than himself. It is known that the integer xor written on the scarf of the other Sunuke-kun calculated by Sunuke-kun with the number $ i $ is $ a_i $. Use this information to identify the integer written on each Sunuke-kun's scarf.
4264 people were able to solve the E problem, and when they solved the D problem, they were in the 2000th place, but in the end, the ranking was not noticeable. Even numbers were the point. I also tried to calculate various formulas in my notebook, but I couldn't come up with a formula to find the answer. I think I can solve it next time, so I would like to say that I have learned.
abc171e.py
n = int(input())
a_list = list(map(int, input().split()))
y = 0
for a in a_list:
y = y ^ a
for a in a_list:
x = y ^ a
print(x, end=" ")
I'm busy this week as well, so I'd like to add it even when I have time.
Thank you for reading the second half to the end.
Recommended Posts