AtCoderBeginnerContest179復習＆まとめ

AtCoder ABC179

2020-09-19(土)に行われたAtCoderBeginnerContest179の問題をA問題から順に考察も踏まえてまとめたものとなります．（時間なかったので，考察は時間があるときに追加します汗）
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

A問題　Plural Form

問題文
AtCoder 王国では、英小文字を用いる高橋語という言語が使われています。
高橋語では、名詞の複数形は次のルールで綴られます。
　・単数形の末尾が"s"以外なら、単数形の末尾に"s"をつける
　・単数形の末尾が"s"なら、単数形の末尾に"es"をつける
高橋語の名詞の単数形$S$が与えられるので、複数形を出力してください。

abc179a.py

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

B問題　Go to Jail

問題文
高橋君は、「サイコロを$2$個振る」という行動を$N$回行いました。$i$回目の出目は$D_{i,1},D_{i,2}$です。
ゾロ目が$3$回以上続けて出たことがあるかどうか判定してください。 より正確には、$D_{i,1}=D_{i,2}$かつ$D_{i+1,1}=D_{i+1,2}$かつ$D_{i+2,1}=D_{i+2,2}$を満たすような$i$が少なくとも一つ存在するかどうか判定してください。

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問題　A x B + C

問題文
正整数$N$が与えられます。$A×B+C=N$を満たす正整数の組$(A,B,C)$はいくつありますか？

abc179c.py

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

D問題　Leaping Tak

問題文
一列に並んだ$N$マスから成るマス目があり、マスには左から順番に$1,2,…,N$の番号がついています。
このマス目で暮らしている高橋君は、現在マス$1$にいて、後述の方法で移動を繰り返してマス$N$へ行こうとしています。
$10$以下の整数$K$と、共通部分を持たない$K$個の区間$[L_1,R_1],[L_2,R_2],…,[L_K,R_K]$が与えられ、これらの区間の和集合を$S$とします。ただし、区間$[l,r]$は$l$以上$r$以下の整数の集合を表します。
　・マス$i$にいるとき、$S$から整数を$1$つ選んで($d$とする)、マス$i+d$に移動する。ただし、マス目の外に出るような移動を行ってはならない。
高橋君のために、マス$N$に行く方法の個数を$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問題　Sequence Sum

問題文
$x$を$m$で割った余りを$f(x,m)$と表します。
初期値$A_1=X$および漸化式$A_{n+1}=f(A_n^2,M)$で定まる数列を$A$とします。
$\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)