ABC344をPythonで（A～F）

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）の解答等のまとめ

A問題

|で分けて最初と最後をくっつける

A

s = input().split("|")
print(s[0] + s[2])

B問題

open(0)をつかうと行数に関係なく標準入力されるデータを取得できる

B

s = open(0).read().split()
for s_i in s[::-1]:
    print(s_i)

C問題

できる和をすべて調べておいて$X_i$と比較する

C

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

s = set()
for a_i in a:
    for b_i in b:
        for c_i in c:
            s.add(a_i + b_i + c_i)

q = int(input())
x = list(map(int, input().split()))
for x_i in x:
    print("Yes" if x_i in s else "No")

D問題

DP：$T$の$i$文字目までを作るのにかかる最小コスト
これを袋ごとに計算していけばよい

D

t = input()
n = int(input())

INF = float("inf")
dp = [0] + [INF] * len(t)

for _ in range(n):
    _, *a = input().split()
    for i in range(len(t) - 1, -1, -1):
        if dp[i] >= INF:
            continue
        for a_i in a:
            if t[i:i + len(a_i)] == a_i:
                dp[i + len(a_i)] = min(dp[i + len(a_i)], dp[i] + 1)

print(dp[-1] if dp[-1] < INF else -1)

E問題

値が重複しないので、各値に対して[それの１つ前の値, それの１つ後ろの値]を記録する。
最後に先頭から順番に$A$を生成すればよい

E

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

head = a[0]
d = dict()
for i in range(n):
    d[a[i]] = [None if i == 0 else a[i - 1],
               None if i == n - 1 else a[i + 1]]

for _ in range(int(input())):
    com = list(map(int, input().split()))
    if com[0] == 1:
        x, y = com[1:]
        z = d[x][1]
        d[x][1] = y
        d[y] = [x, z]
        if z is not None:
            d[z][0] = y
    else:
        x = com[1]
        y, z = d[x]
        d[x] = [None, None]
        if y is None:
            head = z
            d[z][0] = None
        elif z is None:
            d[y][1] = None
        else:
            d[y][1] = z
            d[z][0] = y

ans = []
now = head
while now is not None:
    ans.append(now)
    now = d[now][1]

print(*ans)

F問題

DP：マス$[i, j]$で{通ってきた中で最大の$P$：[行動回数, 所持金]}

そのマスに最小回数で移動してきて、所持金が足りなかったら経路上の$P$が一番高いマスで稼いで戻ってきたとして考えればよい

F

def check(a, b):
    if a[0] != b[0]:
        return min(a, b)
    else:
        return max(a, b)


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

edge = [[[] for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j, r_i in enumerate(list(map(int, input().split()))):
        edge[i][j].append((i, j + 1, r_i))

for i in range(n - 1):
    for j, d_i in enumerate(list(map(int, input().split()))):
        edge[i][j].append((i + 1, j, d_i))

dp = [[dict() for _ in range(n)]  for _ in range(n)]

dp[0][0] = {p[0][0]:[0, 0]}

for i in range(n):
    for j in range(n):
        for key, val in dp[i][j].items():
            for x, y, c in edge[i][j]:
                t = max((c - val[1] + key - 1) // key, 0)
                to_key = max(key, p[x][y])
                if to_key not in dp[x][y]:
                    dp[x][y][to_key] = [float("inf"), 0]
                dp[x][y][to_key] = check(dp[x][y][to_key], [val[0] + t + 1, val[1] + t * key - c])

ans = min(val[0] for val in dp[-1][-1].values())
print(ans)