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.
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))
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)
Recommended Posts