ABC320をPythonで（A~F）

トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)
ページはABC320

A問題

問題文の通りに計算

A

a, b = map(int, input().split())
print(a ** b + b ** a)

B問題

回文になっているか全ての区間で調べる

B

s = input()
ans = 0
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        if s[i:j] == s[i:j][::-1]:
            ans = max(ans, j - i)

print(ans)

C問題

揃う組み合わせがあるか全通りためす。
揃える最小時間は、
3つともおなじなら、それ+2週
2つだけおなじなら、それ+1週
全部違うなら、一番時間がかかるものが答え

C

m = int(input())
s = [input()for _ in range(3)]
INF = float("inf")
ans = INF

for i in range(m):
    for j in range(m):
        if s[0][i] != s[1][j]: continue
        for k in range(m):
            if s[0][i] != s[2][k]: continue

            lst = sorted([i, j, k])
            if lst[0] == lst[2]:
                ans = min(ans, lst[0] + m * 2)
            elif lst[0] == lst[1] or lst[1] == lst[2]:
                ans = min(ans, lst[1] + m)
            else:
                ans = min(ans, lst[2])

print(ans if ans < INF else -1)

D問題

1番の人からbfsをすればいい

D

n, m = map(int,input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a, b, x, y = map(int, input().split())
    edge[a - 1].append((b - 1, x, y))
    edge[b - 1].append((a - 1, -x, -y))

INF = float("inf")
ans = [[INF, INF] for _ in range(n)]
ans[0] = [0, 0]
check = [True] + [False] * (n - 1)
q = deque()
q.append(0)
while q:
    now = q.popleft()
    for to, dx, dy in edge[now]:
        if check[to]: continue
        ans[to] = [ans[now][0] + dx, ans[now][1] + dy]
        check[to] = True
        q.append(to)

for x, y in ans:
    if (x, y) == (INF, INF):
        print("undecidable")
    else:
        print(x, y)

E問題

待っている人と食べている人を分けて考える

各クエリごとに、
1、食べる方にいたが食べ終わった人を待ち列に加える
2、待っている人の中で一番前の人に素麺をあたえる
これをヒープを使って実装する
待ち列側：番号
食事列　：（食べ終わる時間、番号）

E

from heapq import heappop, heappush
n, m = map(int,input().split())

stay = [i for i in range(n)]
eat = []
ans = [0] * n
for _ in range(m):
    t, w, s = map(int,input().split())
    while eat and eat[0][0] <= t:
        _, i = heappop(eat)
        heappush(stay, i)

    if stay:
        now = heappop(stay)
        ans[now] += w
        heappush(eat, (t + s, now))

for ans_i in ans:
    print(ans_i)

F問題

行くときに残るガソリンと帰るときに必要なガソリンの量を同時に考えてDP

F

n, h = map(int, input().split())
x = [0] + list(map(int, input().split()))
gas = [list(map(int, input().split())) for _ in range(n - 1)]

INF = float("inf")
dp = [[0] * (h + 1) for _ in range(h + 1)]

for i in range(n - 1):
    dist = x[i + 1] - x[i]
    p, f = gas[i]
    new_dp = [[INF] * (h + 1) for _ in range(h + 1)]
    for s1 in range(h + 1):
        for s2 in range(h + 1):
            t1, t2 = s1 - dist, s2 + dist 
            if not(0 <= t1 <= h and 0 <= t2 <= h):
                continue
            if t1 > 0 and t2 < h: # まだ移動できるとき
                new_dp[t1][t2] = min(new_dp[t1][t2], dp[s1][s2])

            if t1 >= 0 and t2 < h: # 往路で買う場合
                u1 = min(h, t1 + f)
                new_dp[u1][t2] = min(new_dp[u1][t2], dp[s1][s2] + p)

            if t1 > 0 and f <= t2 <= h: # 復路で買う場合
                if t2 == h:
                    for u2 in range(h - f, h + 1):
                        new_dp[t1][u2] = min(new_dp[t1][u2], dp[s1][s2] + p)
                else:
                    u2 = t2 - f
                    new_dp[t1][u2] = min(new_dp[t1][u2], dp[s1][s2] + p)
    dp = new_dp

dist = (x[-1] - x[-2]) * 2
ans = INF
for i, d_i in enumerate(dp):
    for j, d_j in enumerate(d_i):
        if i - dist >= j:
            ans = min(ans, d_j)

print(ans if ans < INF else -1)