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