Solve Atcoder ABC176 (A, B, C, E) in Python

During the test, I solved 3 questions, A, B, and C. D and E were TLE during the contest.

A - Takoyaki

Comment: Nothing in particular

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

Comment: Nothing in particular (easier than A ...?)

N = int(input())

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

C - Step

Comment: Nothing in particular

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

Comment: I don't know whether to use breadth-first search or depth-first search, For the time being, I tried using depth-first search, which is easy to implement, but TLE. Looking at the explanation, it seems to be solved by breadth-first search, so when I have time Resolve with breadth-first search.

# 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

Comment: The solution was simple, but it became TLE because it was implemented in list during the contest. I haven't been aware of how to use list, set, and tuple in terms of speed, so I'll be careful in the future.

Difference between TLE and 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))

Whole 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)