ABC179 - Atcoder/Python精進のための解説メモ

2020/11/26

ABC179 - A.Plural Form

AtCoder公式 | ABC179 - A.Plural Form

解答

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

要点メモ

  • スライスは便利

ABC179 - B.Go to Jail

AtCoder公式 | ABC179 - B.Go to Jail

解答

n = int(input())
cnt = 0
ans = 'No'
for _ in range(n):
    d1, d2 = map(int, input().split())
    if d1 == d2:
        cnt += 1
        if cnt >= 3:
            ans = 'Yes'
    else:
        cnt = 0
print(ans)

要点メモ

  • 'for _ in range(n)'って'for i in range(n)'よりちょっとだけ早い

ABC179 - C.A x B + C

AtCoder公式 | ABC179 - C.A x B + C

解答

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

要点メモ

  • Cは何でも良いので、A×B<N-1を満たすAを探す問題として解く
  • AごとにBは、N-1/A個となることを覚えておく
  • 計算量を勘違いして勝手に通らないと思い苦戦したので、計算量を正確に見積もるのは大事

ABC179 - D.Leaping Tak

AtCoder公式 | ABC179 - D.Leaping Tak

解答

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353
dp = [0] * n
dp[0] = 1
acc = 0
for i in range(1, n):
    for li, ri in lr:
        if i - li >= 0:
            acc += dp[i - li]
            acc %= mod
        if i - ri - 1 >= 0:
            acc -= dp[i - ri - 1]
            acc %= mod
    dp[i] = acc
print(dp[-1])

要点メモ

  • 普通にDPすると間に合わないので工夫が必要
  • 和集合が連続することを利用して、累積和を使って高速化