ABC339をPythonで（A～E）

日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）の解答等のまとめ

A問題

. で分けて最後を出力

A

print(input().split(".")[-1])

B問題

問題文通りにシミュレーション

B

h, w, n = map(int, input().split())

field = [["."] * w for _ in range(h)]

x, y, arr = 0, 0, 0
array = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for _ in range(n):
    if field[x][y] == ".":
        field[x][y] = "#"
        arr = (arr + 1) % 4
    else:
        field[x][y] = "."
        arr = (arr - 1) % 4

    x = (x + array[arr][0]) % h
    y = (y + array[arr][1]) % w

for f_i in field:
    print("".join(f_i))

C問題

道中で人数が負になったら、その分最初に乗っていたとすればよい

C

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

mini = float("inf")
now = 0
for a_i in a:
    now += a_i
    mini = min(mini, now)

print(sum(a) - min(mini, 0))

D問題

２つの$P$の座標を全通りメモして最小何手でその局面になるかbfsをする
これは、座標を$x \times n + y$の形にして２次元で記録した

D

from collections import deque

n = int(input())
s = [input() for _ in range(n)]

p = []
for i, s_i in enumerate(s):
    for j, s_j in enumerate(s_i):
        if s_j == "P":
            p.append(i * n + j)

INF = 10 ** 9
dp = [[INF] * (n ** 2) for _ in range(n ** 2)]
dp[p[0]][p[1]] = 0
q = deque()
q.append([p[0], p[1]])

array = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def move(p, a):
    x, y = p // n, p % n
    x, y = x + array[a][0], y + array[a][1]
    if 0 <= x < n and 0 <= y < n and s[x][y] != "#":
        return x * n + y
    else:
        return p


while q:
    q_i = deque()
    while q:
        p_1, p_2 = q.popleft()
        for arr in range(4):
            new_p1, new_p2 = move(p_1, arr), move(p_2, arr)
            if dp[new_p1][new_p2] > dp[p_1][p_2] + 1:
                dp[new_p1][new_p2] = dp[p_1][p_2] + 1
                if new_p1 == new_p2:
                    exit(print(dp[new_p1][new_p2]))
                else:
                    q_i.append((new_p1, new_p2))
    q = q_i

print(-1)

E問題

RMQの典型のような問題

E

class SegTree:
    # single update & range get
    def __init__(self, n, ide_ele, seg_func):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 1 << (self.n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.seg_func = seg_func

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.seg_func(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [L, r)のseg_funcしたものを得る
        L: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.seg_func(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.seg_func(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


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

tree = SegTree(maxi + 10, 0, max)

for a_i in a:
    tree.update(a_i, tree.query(max(a_i - d, 1), min(a_i + d, maxi) + 1) + 1)

ans = tree.query(1, maxi + 1)
print(ans)