AtCoderBeginnerContest166 Review & Summary (second 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 second half deals with the DEF 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 I hate Factorization

Problem statement Please indicate one set of integers $ (A, B) $ that satisfies $ A ^ 5−B ^ 5 = X $. However, for a given $ X $, it is guaranteed that there is a set of integers $ (A, B) $ that satisfy the condition. Constraints ・ $ 1 \ leq X \ leq 10 ^ 9 $ ・ $ X $ is an integer. ・ There is a set of integers $ (A, B) $ that satisfy the conditions.

After reading the problem, I thought that every $ X $ had a set of integers $ (A, B) $ that satisfied the condition (too few ...). Even if I input it to a program that implements various patterns of $ X $, there was no output, so I thought that the search range was not enough, so I got stuck. After the contest was over, I read the commentary, and I thought it might be, and when I submitted the implemented program, it was "AC", so I should have submitted it ...

abc166d.py


x = int(input())
flag = 0
for a in range(-200, 201):
    if flag == 1:
        break
    for b in range(-200, 201):
        if a**5 - b**5 == x:
            print(a, b)
            flag = 1
            break

E problem This Message Will Self-Destruct in 5s

Problem statement As a talented agent in the Kingdom of AtCoder, you have infiltrated a party on the trading floor to prevent stolen confidential information from falling into the hands of the Kingdom of AlDebaran. The party has $ N $ participants, each numbered from $ 1 $ to $ N $. Participant $ i $ is $ A_i $ tall. Through prior cross-examination, you know that trading confidential information is for $ 2 $ people who meet the following conditions: ・ The absolute value of the difference in numbers held by $ 2 $ people is equal to the sum of the heights of $ 2 $ people. There are $ \ frac {N (N−1)} {2} $ ways to select $ 2 $ participants from $ N $ participants and pair them, but the pair that meets the above conditions is How many ways are there? In addition, you do not know what the contents of confidential information are.

When I participated in the contest, I was stuck with the D problem and couldn't solve the E problem because I didn't have much time, but I want to be able to solve this level of problem. I have been conscious of "E problem F problem = difficult problem", and it is difficult to solve it during the contest. I implemented what is written in the commentary article and got "AC" safely with the following code.

abc166e.py


n = int(input())
a_list = list(map(int, input().split()))
l_dict = {}
ans = 0
for i in range(0, n):
    a = a_list[i]
    ri = i - a
    if ri in l_dict:
        ans += l_dict[ri]
    li = i + a
    if li in l_dict:
        l_dict[li] += 1
    else:
        l_dict[li] = 1
print(ans)

I was confused by the expression of the absolute value of the difference between the numbers of $ 2 $ people. If you think about it carefully, you could add a condition of $ i <j $ when you chose two people. When it is negative, it seems difficult to process the absolute value. When I thought about it, the loss was confirmed, so I don't want to think it's difficult.

F problem Three Variables Game

Problem statement In some games there are $ 3 $ variables, represented by $ A, B and C $ respectively. As the game progresses, you will be forced to make $ N $ choices. Each selection is indicated by the string $ s_i $, where when $ s_i $ is "AB", add $ 1 $ to either $ A $ or $ B $ and subtract $ 1 $ from the other, "AC" When, add $ 1 $ to either $ A $ or $ C $ and subtract $ 1 $ from the other, and when "BC", add $ 1 $ to either $ B $ or $ C $ and the other Means to subtract $ 1 $ from. Neither $ A, B, C $ can be negative after any selection. Determine if it is possible to complete all selections $ N $ times while satisfying this condition, and if so, indicate one such selection method.

I read the commentary and just implemented what was written. It seems difficult to notice that you have to be careful about the processing only when $ A + B + C = 2 $ because there is no input example. I want to be able to solve these problems during the contest.

abc166f.py


def check(s):
    if dict_x[s[0]] == 0 and dict_x[s[1]] == 0:
        return "NOT"
    elif  dict_x[s[0]] > 0 and dict_x[s[1]] == 0:
        return s[1]
    elif  dict_x[s[0]] == 0 and dict_x[s[1]] > 0:
        return s[0]
    elif dict_x[s[0]] == 1 and dict_x[s[1]] == 1:
        return "EVEN"
    else:
        if dict_x[s[0]] > dict_x[s[1]]:
            return s[1]
        else:
            return s[0] 
def update(s, mozi):
    if s[1] == mozi:
        dict_x[s[0]] -= 1
        dict_x[s[1]] += 1
    else:
        dict_x[s[0]] += 1
        dict_x[s[1]] -= 1
n, a, b, c = map(int, input().split())
dict_x = {"A": a, "B": b, "C": c}
s_list = []
ans_list = []
flag = 1
for i in range(0, n):
    s = input()
    s_list.append(s)
if a + b + c == 0:
    flag = 0
elif a + b + c == 1:
    for s in s_list:
        x = check(s)
        if x == "NOT":
            flag = 0
            break
        else:
            ans_list.append(x)
            update(s, x)
elif a + b + c == 2:
    i = 0
    for s in s_list:
        x = check(s)
        if x == "NOT":
            flag = 0
            break
        elif x == "EVEN":
            if i == len(s_list) - 1:
                ans_list.append(s[0])
                update(s, x)
            elif s == s_list[i + 1]:
                ans_list.append(s[0])
                update(s, x)
            else:
                if s[0] in s_list[i + 1]:
                    ans_list.append(s[0])
                    update(s, s[0])
                else:
                    ans_list.append(s[1])
                    update(s, s[1])
        else:
            ans_list.append(x)
            update(s, x)
        i += 1
else:
    for s in s_list:
        x = check(s)
        if x == "NOT":
            flag = 0
            break
        elif x == "EVEN":
            ans_list.append(s[0])
            update(s, s[0])
        else:
            ans_list.append(x)
            update(s, x)
if flag == 1:
    print("Yes")
    for ans in ans_list:
        print(ans)
else:
    print("No")

When I review the F problem and the code I wrote myself, I realize that there is still a lot of waste. 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)
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)
AtCoderBeginnerContest180 Review & Summary
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
Django Girls Tutorial Summary First Half