ABC383をPythonで(A~D)

大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383）の解答等の速報的まとめ

A問題

水を入れる時刻のたびに水がいくら減ったか計算する。
制約からするに、１単位時間ごとに計算しても問題ない

A

n = int(input())
water = 0
last = 0
for _ in range(n):
    t, v = map(int, input().split())
    water = max(0, water - (t - last))
    water += v
    last = t

print(water)

B問題

加湿器を置く場所を全通り試す

B

def calc(a, b, x, y):
    res = 0
    for i, s_i in enumerate(s):
        for j, s_ij in enumerate(s_i):
            if s_ij == "." and (abs(a - i) + abs(b - j) <= d or abs(x - i) + abs(y - j) <= d):
                res += 1
    return res


h, w, d = map(int, input().split())
s = [input() for _ in range(h)]

ans = 0
for x1 in range(h):
    for y1 in range(w):
        if s[x1][y1] == "#":
            continue
        for x2 in range(h):
            for y2 in range(w):
                if (x1, y1) == (x2, y2) or s[x2][y2] == "#":
                    continue
                ans = max(ans, calc(x1, y1, x2, y2))

print(ans)

C問題

dfsで計算する

C

def calc(a, b, x, y):
    res = 0
    for i, s_i in enumerate(s):
        for j, s_ij in enumerate(s_i):
            if s_ij == "." and (abs(a - i) + abs(b - j) <= d or abs(x - i) + abs(y - j) <= d):
                res += 1
    return res


h, w, d = map(int, input().split())
s = [input() for _ in range(h)]

ans = 0
for x1 in range(h):
    for y1 in range(w):
        if s[x1][y1] == "#":
            continue
        for x2 in range(h):
            for y2 in range(w):
                if (x1, y1) == (x2, y2) or s[x2][y2] == "#":
                    continue
                ans = max(ans, calc(x1, y1, x2, y2))

print(ans)

D問題

約数が奇数個のとき必ず平方数になっている。
約数が９個になるのは

• 素数1種類の8乗
• 素数2種類の積の2乗

のパターンのみなので、それがいくつあるか計算する。

D

import bisect

prime = [True] * (10 ** 6 + 1)
prime[0] = prime[1] = False

for i in range(2, 10 ** 3 + 10):
    if prime[i]:
        for j in range(i * i, 10 ** 6 + 1, i):
            prime[j] = False

n = int(input())
lst = []
ans = 0
for i in range(2, 10 ** 6 + 1):
    if prime[i]:
        if lst:
            ans += bisect.bisect(lst, n // (i ** 2))
        lst.append(i ** 2)
        if i ** 8 <= n:
            ans += 1

print(ans)