Résoudre Atcoder ABC176 (A, B, C, E) en Python

Pendant le test, j'ai résolu 3 questions, A, B et C. D et E étaient TLE pendant le concours.

A - Takoyaki

Commentaire: rien de particulier

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

Commentaire: Rien de particulier (plus facile que A ...?)

N = int(input())

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

C - Step

Commentaire: rien de particulier

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

Commentaire: Je ne sais pas s'il faut utiliser la recherche de priorité de largeur ou la recherche de priorité de profondeur, Pour le moment, j'ai essayé d'utiliser la recherche de priorité en profondeur, qui est facile à mettre en œuvre, mais TLE. En regardant l'explication, cela semble être résolu par la recherche de priorité de largeur, donc quand j'ai le temps Résoudre avec la recherche de priorité de largeur.

# 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

Commentaire: La solution était simple, mais elle est devenue TLE car elle a été implémentée en liste lors du concours. Je ne savais pas comment utiliser list, set et tuple en termes de vitesse, je ferai donc attention à l'avenir.

Différence entre TLE et 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))

Code entier

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)