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 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 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")
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)
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)
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