AtCoderBeginnerContest177 Review & Summary (first half)

AtCoder ABC177 This is a summary of the problems of AtCoder Beginner Contest 177, which was held on Saturday, 2020-08-29, in order from problem A, taking into consideration the consideration. The first half deals with problems up to ABC. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

Problem A Don't be late

Problem statement Takahashi is meeting with Aoki. The meeting place is $ D $ meters away from Takahashi's house, and the meeting time is $ T $ minutes later. Takahashi is leaving home now and will move straight to the meeting place at $ S $ meters per minute. Will you be in time for the meeting?

abc177a.py


d, t, s  = map(int, input().split())
if d <= t * s:
    print("Yes")
else:
    print("No")

Problem B Substring

Problem statement $ 2 $ Two strings $ S, T $ are given. Rewrite some characters in $ S $ so that $ T $ is a substring of $ S $. At least how many characters do I need to rewrite? However, a substring is a continuous substring. For example,'xxx' is a substring of'yxxxy', but not a substring of'xxyxx'.

Since $ S and T $ are more than $ 1 $ characters and less than $ 1000 $ characters, all possibilities can be calculated in time. For example, considering the 7-character'abcdefg'and the 3-character'efh', how many characters need to be rewritten for each of'abc','bcd','cde','def', and'efg'. Is calculated, and the smallest one is the answer.

abc177b.py


s = input()
t = input()
min_count = 1000
for i in range(len(s) - len(t) + 1):
    count = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            count += 1
    min_count = min(count, min_count)
    if min_count == 0:
        break
print(min_count)

C problem Substring

Problem statement $ N $ integers $ A_1,…, A_N $ are given. $ 1 \ leq i <j \ leq Find the sum of $ A_i × A_j $ for all pairs $ (i, j) $ that satisfy N $ with $ mod (10 ^ 9 + 7) $.

The sum to be calculated is $ A_1 × (A_2 + ... + A_N) + A_2 × (A_3 + ... + A_N) + ... + A_ {N-1} × (A_N) $, so all are calculated individually. The amount of calculation can be reduced rather than doing.

abc177c.py


n = int(input())
a_list = list(map(int, input().split()))
ans = 0
total = 0
mod = 10 ** 9 + 7
for i in range(n):
    total += a_list[i]
    if total >= mod:
        total = total % mod
for i in range(n - 1):
    total -= a_list[i]
    if total < 0:
        total += mod
    ans += a_list[i] * total
    if ans >= mod:
        ans = ans % mod
print(ans)

This is the end of the first half. Recently, the official commentary has been described very carefully, so I hope you can refer to that for the detailed solution. Thank you for reading to the end of the first half.

The second half will explain the DE problem. Continued in the second half.

Recommended Posts

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)
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)
AtCoderBeginnerContest171 Review & Summary (second half)
AtCoderBeginnerContest174 Review & Summary (second half)
AtCoderBeginnerContest173 Review & Summary (second half)
AtCoderBeginnerContest177 Review & Summary (second half)
AtCoderBeginnerContest180 Review & Summary
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
Django Girls Tutorial Summary First Half
AtCoder Review of past questions (first half of 12 / 8,9)