Löse den Atcoder ABC176 (A, B, C, E) in Python

Während des Tests habe ich 3 Fragen gelöst, A, B und C. D und E waren während des Wettbewerbs TLE.

A - Takoyaki

Kommentar: Nichts besonderes

N, X, T = map(int, input().split())

if N % X == 0:
    print(N // X * T)
else:
    print((N // X + 1) * T)

B - Multiple of 9

Kommentar: Nichts besonderes (einfacher als A ...?)

N = int(input())

if N % 9 == 0:
    print("Yes")
else:
    print("No")

C - Step

Kommentar: Nichts besonderes

N = int(input())
A_L = [int(x) for x in input().split()]

ans = 0
_a = A_L[0]
for i in range(1, N):
    _ca = A_L[i]
    ans += max(_a - _ca, 0)
    _a = max(_ca, _a)

print(ans)

D - Wizard in Maze

Kommentar: Ich weiß nicht, ob ich die Breitenprioritätssuche oder die Tiefenprioritätssuche verwenden soll. Vorerst habe ich versucht, die Tiefenprioritätssuche zu verwenden, die einfach zu implementieren ist, aber TLE. Wenn ich mir die Erklärung anschaue, scheint sie durch die Suche nach Breitenpriorität gelöst zu werden, wenn ich also Zeit habe Mit Breitenprioritätssuche auflösen.

# TLE
import sys

sys.setrecursionlimit(10**9)

H, W = map(int, input().split())
C_L = [int(_)-1 for _ in input().split()]
D_L = [int(_)-1 for _ in input().split()]
S_L = [[x for x in input()] for y in range(H)]


ans = 0
c_l = [[float("Inf")] * W for _ in range(H)]


def dfs(x, y, c):
    if not(0 <= x < W) or not(0 <= y < H) or S_L[y][x] == "#":
        return
    if c_l[y][x] > c:
        c_l[y][x] = c

        # no magic
        dfs(x+1, y, c)
        dfs(x-1, y, c)
        dfs(x, y+1, c)
        dfs(x, y-1, c)

        # use magic
        for _x in range(-2, 3):
            for _y in range(-2, 3):
                if (_x == -1 and _y == 0) or (_x == 1 and _y == 0)\
                        or (_x == 0 and _y == -1) or (_x == 0 and _y == 1)\
                        or (_x == 0 and _y == 0):
                    continue
                dfs(x+_x, y+_y, c+1)


dfs(C_L[1], C_L[0], 0)

if c_l[D_L[0]][D_L[1]] == float("Inf"):
    print("-1")
else:
    print(c_l[D_L[0]][D_L[1]])

E - Bomber

Kommentar: Die Lösung war einfach, wurde jedoch zu TLE, da sie während des Wettbewerbs in der Liste implementiert wurde. Ich war mir nicht bewusst, wie man Listen, Einstellungen und Tupel in Bezug auf die Geschwindigkeit verwendet, daher werde ich in Zukunft vorsichtig sein.

Unterschied zwischen TLE und AC

TLE

HW_L = [[int(x)-1 for x in input().split()] for y in range(M)]

AC

HW_L = set(tuple(int(x)-1 for x in input().split()) for y in range(M))

Ganzer Code

H, W, M = map(int, input().split())
HW_L = set(tuple(int(x)-1 for x in input().split()) for y in range(M))

w_l = [0] * W
h_l = [0] * H

for _hi, _wi in HW_L:
    w_l[_wi] += 1
    h_l[_hi] += 1

max_h = max(h_l)
max_w = max(w_l)

h_idx = [i for i, x in enumerate(h_l) if x == max_h]
w_idx = [i for i, x in enumerate(w_l) if x == max_w]

ans = max_h + max_w - 1

for hi in h_idx:
    for wj in w_idx:
        if (hi, wj) not in HW_L:
            ans = max_h + max_w
            break
    else:
        continue
    break

print(ans)