AtCoderBeginnerContest179 Review & Summary

AtCoder ABC179 This is a summary of the problems of AtCoder Beginner Contest 179, which was held on Saturday, 2020-09-19, in order from problem A, taking into consideration the consideration. (I didn't have time, so I'll add some thoughts when I have time. Sweat) The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

Problem A Plural Form

Problem statement In the Kingdom of AtCoder, the language Takahashi, which uses lowercase letters, is used. In Takahashi, the plural forms of nouns are spelled according to the following rules. ・ If the singular form ends with something other than "s", add "s" to the end of the singular form. ・ If the singular ends with "s", add "es" to the end of the singular Given the singular $ S $ of the Takahashi noun, output the plural.

abc179a.py


n = input()
if n[-1] == "s":
    print(n + "es")
else:
    print(n + "s")

Problem B Go to Jail

Problem statement Mr. Takahashi performed the action of "rolling $ 2 $ dice" $ N $ times. The $ i $ roll is $ D_ {i, 1}, D_ {i, 2} $. Determine if getting doublet has appeared more than $ 3 $ in a row. More precisely, $ D_ {i, 1} = D_ {i, 2} $ and $ D_ {i + 1,1} = D_ {i + 1,2} $ and $ D_ {i + 2,1} Determine if there is at least one $ i $ that satisfies = D_ {i + 2,2} $.

abc179b.py


n = int(input())
check_list = []
for i in range(n):
    d1, d2 = map(int, input().split())
    if d1 == d2:
        check_list.append(1)
    else:
        check_list.append(0)
flag = 0
for i in range(n - 2):
    if sum(check_list[i:(i+3)]) == 3:
        flag = 1
        break
if flag:
    print("Yes")
else:
    print("No")

C problem A x B + C

Problem statement Given a positive integer $ N $. How many pairs of positive integers $ (A, B, C) $ satisfy $ A × B + C = N $?

abc179c.py


n = int(input())
count = 0
for a in range(1, n):
    count += (n - 0.5) // a
print(int(count))
print(count)

D problem Leaping Tak

Problem statement There are squares consisting of $ N $ squares in a row, and the squares are numbered $ 1,2,…, N $ in order from the left. Mr. Takahashi, who lives in this square, is currently in the square $ 1 $ and is trying to go to the square $ N $ by repeating the movement by the method described later. An integer $ K $ less than or equal to $ 10 $ and $ K $ intervals $ [L_1, R_1], [L_2, R_2],…, [L_K, R_K] $ that have no intersection are given, and these intervals Let the union of be $ S $. However, the interval $ [l, r] $ represents a set of integers greater than or equal to $ l $ and less than or equal to $ r $. ・ When you are in the mass $ i $, select an integer $ 1 $ from $ S $ (let's call it $ d $) and move it to the mass $ i + d $. However, you must not move out of the square. For Takahashi, find the remainder of the number of ways to get to the mass $ N $ divided by $ 998244353 $.

abc179d.py


n, k = map(int, input().split())
s_list = []
a_list = [0] * (n + 1)
b_list = [0] * (n + 1)
a_list[1] = 1
b_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])
for i in range(2, n + 1):
    for l, r in s_list:
        t2 = max(0, i - l)
        t1 = max(0, i - r)
        a_list[i] += b_list[t2] - b_list[t1]
    b_list[i] = (b_list[i - 1] + a_list[i]) % 998244353
print(a_list[n] % 998244353)

E problem Sequence Sum

Problem statement The remainder of $ x $ divided by $ m $ is expressed as $ f (x, m) $. Let $ A $ be a sequence of numbers defined by the initial value $ A_1 = X $ and the recurrence formula $ A_ {n + 1} = f (A_n ^ 2, M) $. Find $ \ sum_ {i = 1} ^ {N} A_i $.

abc179e.py


n, x, m = map(int, input().split())
x_set = set()
x_list = []
for i in range(n):
    if x not in x_set:
        x_set.add(x)
        x_list.append(x)
    else:
        break
    x = x**2 % m
total = 0
start = n
for i in range(n):
    if x_list[i] == x:
        start = i
        break
    else:
        total += x_list[i]
if start != n:
    m = len(x_list) - start
    k = (n - start) // m
    total += k * sum(x_list[start:])
    for i in range(0, n - k * m - start):
        total += x_list[start + i]
print(total)

Recommended Posts

AtCoderBeginnerContest180 Review & Summary
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
AtCoderBeginnerContest179 Review & Summary
AtCoderBeginnerContest178 Review & Summary (second half)
AtCoderBeginnerContest175 Review & Summary (first half)
AtCoderBeginnerContest161 Review & Summary (second half)
AtCoderBeginnerContest164 Review & Summary (second half)
AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest169 Review & Summary (first half)
AtCoderBeginnerContest176 Review & Summary (second half)
AtCoderBeginnerContest174 Review & Summary (first half)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest168 Review & Summary (second half)
AtCoderBeginnerContest169 Review & Summary (second half)
AtCoderBeginnerContest165 Review & Summary (first half)
AtCoderBeginnerContest170 Review & Summary (first half)
AtCoderBeginnerContest167 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (second half)
AtCoderBeginnerContest177 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (second half)
AtCoderBeginnerContest168 Review & Summary (first half)
AtCoderBeginnerContest174 Review & Summary (second half)
AtCoderBeginnerContest178 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (first half)
AtCoderBeginnerContest161 Review & Summary (first half)
AtCoderBeginnerContest173 Review & Summary (second half)
AtCoderBeginnerContest172 Review & Summary (first half)
AtCoderBeginnerContest177 Review & Summary (second half)
AtCoderBeginnerContest176 Review & Summary (first half)
Python Summary
samba summary
python-pptx summary
Linux Summary
Python summary
Django Summary
pyenv summary
String summary 1
pytest summary
matplotlib summary
Function review