ABC325をPythonで（A~G）

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

https://atcoder.jp/contests/abc325

# A問題
```python:A
s,t = input().split()
print(f"{s} san")
```
# B問題
各時間ごとにそのタイミングで開始したら何人参加できるかを全探索する
```python: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問題
```python: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に入れる
1. heapの中で出ていく時間が早いものから印刷可能か確かめる
1. heapが空っぽの場合は、次に入ってくるものの時間まで飛ばす

```python: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問題
ダイクストラ
今車に乗っているか否かを保持して調べる
```python: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問題
[公式解説](https://atcoder.jp/contests/abc325/editorial/7449)のとおり
```python: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問題
[公式解説](https://atcoder.jp/contests/abc325/editorial/7486)のとおり
```python: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])
```