AtCoderBeginnerContest171 Review & Summary (second half)

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

D problem Replacing

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.

E problem Red Scarf

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

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)
AtCoderBeginnerContest175 Review & Summary (first half)
AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest169 Review & Summary (first half)
AtCoderBeginnerContest174 Review & Summary (first half)
AtCoderBeginnerContest173 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)
AtCoderBeginnerContest180 Review & Summary
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
AtCoderBeginnerContest179 Review & Summary
Django Girls Tutorial Summary First Half