ABC348をPythonで（A～D）+Eの感想

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

A問題

ooxを$N$個以上まで増やして、そこからスライス

A

s = "oox" * 50
print(s[:int(input())])

B問題

距離を計算して一番遠いところを答える
ただ、ルートをとると小数点の計算になって精度誤差が怖いのでルートをとる前で比較する

B

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

for x, y in p:
    ans = 0
    dist = 0
    for i, (x_i, y_i) in enumerate(p, 1):
        if dist < (x_i - x) ** 2 + (y_i - y) ** 2:
            dist = (x_i - x) ** 2 + (y_i - y) ** 2
            ans = i
    print(ans)

C問題

同じ色の中で最小値は何かを調べて、その色別の値の中で最大値を答える問題
色ごとに、同じ色は$A_i$が昇順になるようにソートして順に見ると、各色ごとに最初に現れる値が最小値になるからそれらを大小比較すればよい

C

n = int(input())

data = [list(map(int, input().split())) for _ in range(n)]
data.sort(key=lambda x: (x[1], x[0]))

ans = 0
for i in range(n):
    if i > 0 and data[i - 1][1] == data[i][1]:
        continue
    ans = max(ans, data[i][0])

print(ans)

D問題

ダイクストラ
現状エネルギー最大でその場所へ来た時に、薬がありかつエネルギーより大きい値になるときその薬を使う
あとはエネルギーを正負反転させてダイクストラをすればいい

D

from heapq import heappop, heappush


def max_pop(q):
    a = heappop(q)
    a[0] *= -1
    return a


def max_push(q, x):
    x[0] *= -1
    heappush(q, x)


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

sx, sy, gx, gy = 0, 0, 0, 0
for i, a in enumerate(field):
    for j, a_j in enumerate(a):
        if a_j == "S":
            sx, sy = i, j
        if a_j == "T":
            gx, gy = i, j

n = int(input())
d = [[0] * w for _ in range(h)]
for _ in range(n):
    r_i, c_i, e_i = map(int, input().split())
    d[r_i - 1][c_i - 1] = e_i

q = list()
q.append([0, sx, sy])

E = [[-1] * w for _ in range(h)]

while q:
    e_i, x, y = max_pop(q)
    if E[x][y] > e_i:
        continue
    if e_i < d[x][y]:
        e_i = d[x][y]
        E[x][y] = e_i

    if e_i == 0:
        continue

    for x_i, y_i in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
        if 0 <= x_i < h and 0 <= y_i < w and field[x_i][y_i] != "#" and E[x_i][y_i] < e_i - 1:
            E[x_i][y_i] = e_i - 1
            max_push(q, [e_i - 1, x_i, y_i])

print("Yes" if E[gx][gy] >= 0 else "No")

E問題

全方位木DPにしか見えなくて色々わちゃわちゃやってたができなかった。
木の重心の解説がなぜ正解できるかわからない
なんでみんなできてるの？

• やってたこと
  • 最初のスコアをDFSで計算
  • しながらその枝へ移動したらいくつ変わるかの差分を求める
  • 減る方向にのみ移動しながら計算
  • この方法でMLEしてダメだった