AtCoderBeginnerContest172 Review & Summary (first half)

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 A Calc

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 B Minor Change

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)

C problem Tsundoku

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)

D problem Sum of Divisors

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

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)
AtCoderBeginnerContest161 Review & Summary (first half)
AtCoderBeginnerContest172 Review & Summary (first half)
AtCoderBeginnerContest176 Review & Summary (first half)
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)
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest179 Review & Summary
Django Girls Tutorial Summary First Half
AtCoder Review of past questions (first half of 12 / 8,9)