AtCoder Beginner Contest 172の感想

ABC172に参加した。

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Calc

やるだけ。

a = int(input())
ans = a + a ** 2 + a ** 3
print(ans)

B – Minor Change

SとTを前から順番に1文字ずつ比較していく。

s = input()
t = input()

ans = 0
for i in range(len(s)):
    if s[i] != t[i]:
        ans += 1

print(ans)

C – Tsundoku

AとBからそれぞれx冊、y冊読んで、x+yを最大化する問題。

AとBの累積和をO(N)で用意し、片方を固定してもう片方を二分探索もしくは尺取りで探索する。

import bisect

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cum_a = [0]
for i in range(n):
    cum_a.append(cum_a[i] + a[i])

cum_b = [0]
for i in range(m):
    cum_b.append(cum_b[i] + b[i])

ans = 0
for i in range(n + 1):
    if cum_a[i] > k:
        break

    val = bisect.bisect_right(cum_b, k - cum_a[i]) - 1
    ans = max(ans, i + val)

print(ans)

D – Sum of Divisors

実行時間がいつもより多めの3秒。

ABC170-Dと似てる。

D - Not Divisible

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

こちらの解説が大変分かりやすい。

AtCoder Beginner Contest 172 D - Sum of Divisors - Crieit

問題文要約： k=1からNまで、を足し上げる。ただし、とは、正の整数であって、kの約数であるものの個数。 O(N^2) ...

1からnまでループを回し、n // i までの等差数列の和を足し込んでいく。

n = int(input())

ans = 0
for i in range(1, n + 1):
    limit = n // i
    ans += (limit * (limit + 1) // 2) * i

print(ans)

2完しか出来ず、レートが下がってしまった。

Dは最近類題が出ていただけに、知識が身についていないことを痛感した。