ABC415をPythonで（A～E）

日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415）の解答等の速報的まとめ

A問題

問題文通りに実装

A

n = int(input())
a = list(map(int, input().split()))
print("Yes" if int(input()) in a else "No")

B問題

#の場所をリストに入れる
zipを使って奇数番目と偶数番目を順番に出力する

B

s = input()
lst = [str(i + 1) for i, s_i in enumerate(s) if s_i == "#"]

for l_i, l_j in zip(lst[::2], lst[1::2]):
    print(l_i + "," + l_j)

C問題

問題文のbit管理の要領でdpをする
bitDPの練習問題のようなもの

C

for _ in range(int(input())):
    n = int(input())
    s = "0" + input()
    dp = [False] * (1 << n)
    dp[0] = True

    for bit in range(1 << n):
        if not dp[bit]:
            continue
        for i in range(n):
            if bit >> i & 1:
                continue
            new_bit = bit + (1 << i)
            if s[new_bit] == "0":
                dp[new_bit] = True

    print("Yes" if dp[-1] else "No")

D問題

交換できるショップの中でコーラ瓶の減少が一番少ない所を選んで交換する

D

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

lst.sort(key=lambda x:x[1] - x[0])
ans = 0
while lst and n > 0:
    a_i, b_i = lst.pop()
    if a_i <= n:
        seal = (n - b_i) // (a_i - b_i)
        ans += seal
        n = n - a_i * seal + b_i * seal
print(ans)

E問題

ゴールから逆算で必要になるコインの最小枚数を計算する
なお$(0,0)$からDFSをするとMLEになる

E

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

que = list()
for i in range(h):
    for j in range(w):
        a[i][j] -= p[i + j]
        que.append((i, j))

que.sort(key=sum, reverse=True)
for x, y in que:
    lst = list()
    for i, j in [(x + 1, y), (x, y + 1)]:
        if 0 <= i < h and 0 <= j < w:
            lst.append(a[i][j])

    res = 0
    if lst and max(lst) < 0:
        res = max(lst)
    a[x][y] = res + a[x][y]

print(max(a[0][0] * -1, 0))