AtCoder ABC172 This is a summary of the AtCoder Beginner Contest 172 problems that took place on Saturday, 2020-06-27, starting with problem A and taking into consideration the considerations. 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 The integer $ a $ is entered. Output the value $ a + a ^ 2 + a ^ 3 $.
abc172a.py
a = int(input())
print(a + a**2 + a**3)
Problem statement Given the strings $ S, T $. When changing $ S $ to $ T $ by repeating the following operations, find the minimum number of operations. Operation: Select the $ 1 $ character of $ S $ and rewrite it with another character
I checked with the for statement whether each character matches from the beginning.
abc172b.py
s = input()
t = input()
count = 0
for i in range(len(s)):
if s[i] != t[i]:
count +=1
print(count)
Problem statement There are two desks A and B. Desk A has $ N $ books and Desk B has $ M $ books stacked vertically. The $ (1 \ leq i \ leq N) $ book currently loaded on desk A at the $ i $ position from the top takes $ A_i $ minutes to read, and the book $ on desk B is currently $ i $ th from the top The book $ (1 \ leq i \ leq M) $ loaded in is required to read $ B_i $. Consider the following actions. ・ Select the desk where the books remain, read the books on the top of the desk, and remove them from the desk. How many books can you read when you repeat this action so that the total travel time does not exceed $ K $? Ignore the time it takes other than reading a book.
For the time being, I thought I would solve it by recursion, but it was clear that it would take time to execute, so I wrote the code with various ingenuity. I wanted to be able to write it so simply by including the reference code of python in the explanation.
abc172c.py
n, m, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
new_a_list = [[0, 0]]
a_sum = 0
for i in range(0, n):
a_sum += a_list[i]
if a_sum <= k:
new_a_list.append([i + 1, a_sum])
else:
break
best = len(new_a_list) - 1
b_sum = 0
a_sum = new_a_list[-1][1]
a_count = new_a_list[-1][0]
flag = 1
for i in range(0, m):
b_sum += b_list[i]
while True:
if b_sum <= k - a_sum:
if best < i + 1 + a_count:
best = i + 1 + a_count
break
if a_count == 0:
flag = 0
break
a_count -= 1
a_sum = new_a_list[-(len(new_a_list) - a_count)][1]
if flag == 0:
break
print(best)
Problem statement Let $ f (X) $ be the number of positive divisors of $ X $ for a positive integer $ X $. Given a positive integer $ N $, find $ \ sum_ {K = 1} ^ {N} K × f (K) $.
Overwhelming lack of math skills (sweat) I couldn't solve it, so I could solve it by implementing what was written in the explanation.
abc172d.py
n = int(input())
total = 0
for j in range(1, n + 1):
x = j
y = n // x
total += y * (y + 1) * x // 2
print(total)
The implementation is simple but I couldn't think of it, and the execution time limit: 3 sec was overlooked in the first place. (I don't think it can be solved even if it is not overlooked)
This is the end of the first half. 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