ABC325をPythonで（A~G）

キーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）

A問題

A

s,t = input().split()
print(f"{s} san")

B問題

各時間ごとにそのタイミングで開始したら何人参加できるかを全探索する

B

n = int(input())
data = [list(map(int, input().split()))for _ in range(n)]

ans = 0
for i in range(24):
    cnt = 0
    for w, x in data:
        if x <= i < x + 9 or x - 24 <= i < x - 24 + 9:
            cnt += w
    ans = max(ans, cnt)

print(ans)

C問題

シンプルbfs問題

C

from collections import deque

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

group = [[0] * w for _ in range(h)]
q = deque()
cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#" and group[i][j] == 0:
            cnt += 1
            q.append((i, j))
            group[i][j] = cnt
            while q:
                x,y = q.popleft()
                for x_i, y_i in [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1)]:
                    if 0 <= x_i < h and 0 <= y_i < w and s[x_i][y_i] == "#" and group[x_i][y_i] < cnt:
                        group[x_i][y_i] = cnt
                        q.append((x_i, y_i))

print(cnt)

D問題

貪欲にやっていく

1. 次の印刷時間に入ってくるものをheapに入れる
2. heapの中で出ていく時間が早いものから印刷可能か確かめる
3. heapが空っぽの場合は、次に入ってくるものの時間まで飛ばす

D

from heapq import heappop, heappush

n = int(input())
data = []
for _ in range(n):
    t, d = map(int, input().split())
    data.append((t, t + d))

data.sort()
last = 0
ans = 0
q = []
i = 0
while True:
    while i < n and data[i][0] <= last + 1:
        heappush(q, data[i][1])
        i += 1

    if q:
        x = heappop(q)
        if last + 1 <= x:
            ans += 1
            last += 1
    elif i < n:
        last = data[i][0] - 1
    else:
        break

print(ans)

E問題

ダイクストラ
今車に乗っているか否かを保持して調べる

E

from heapq import heappop, heappush

n, a, b, c = map(int, input().split())
d = [list(map(int, input().split()))for _ in range(n)]

q = [[0, 0, 1]]
time = [[float("inf")] * 2 for _ in range(n)]
time[0][0] = 0
while q:
    t_i, now, is_car = heappop(q)
    if time[now][is_car] < t_i: continue
    for to in range(n):
        if is_car:
            if time[to][1] > t_i + d[now][to] * a:
                time[to][1] = t_i + d[now][to] * a
                heappush(q, [time[to][1], to, 1])
        if time[to][0] > t_i + d[now][to] * b + c:
            time[to][0] = t_i + d[now][to] * b + c
            heappush(q, [time[to][0], to, False])

print(min(time[-1]))

F問題

公式解説のとおり

F

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

def ceil_div(x, y):# 切り上げ計算用
    return (x + y - 1) // y

dp = [0] * (a[2] + 1)
INF = float("inf")
for d in D:
    new_dp = [INF] * (a[2] + 1)
    for i in range(a[2] + 1):
        for j in range(i + 1):
            new_dp[i] = min(new_dp[i], dp[j] + max(0, ceil_div(d - a[0] * (i - j), b[0])))
    dp = new_dp

ans = INF
for i, j in enumerate(dp):
    if j <= b[2]:
        ans = min(ans, i * a[1] + j * b[1])

print(ans if ans < INF else -1)

G問題

公式解説のとおり

G

s = input()
k = int(input())
n = len(s)

dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(n + 1):
        dp[i][j] = j - i if i <= j else float("inf")

for length in range(n + 1):
    for left in range(n):
        right = left + length
        if right > n:break

        dp[left][right] = length
        for i in range(left + 1, right):
            dp[left][right] = min(dp[left][right], dp[left][i] + dp[i][right])
            if s[left] == "o" and s[i] == "f" and (i == left + 1 or dp[left + 1][i] == 0):
                dp[left][right] = min(dp[left][right], max(0, dp[i + 1][right] - k))

print(dp[0][n])