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)

Recommended Posts

Solve Atcoder ABC176 (A, B, C, E) in Python
Solve ABC175 A, B, C in Python
Solve ABC036 A ~ C in Python
Solve ABC037 A ~ C in Python
Solve ABC165 A, B, D in Python
AtCoder ABC 177 Python (A ~ E)
AtCoder ABC 178 Python (A ~ E)
Solve ABC176 E in Python
Solve ABC163 A ~ C with Python
ABC127 A, B, C Explanation (python)
ABC166 in Python A ~ C problem
Solve Atcoder ABC169 A-D in Python
Solve ABC168 A ~ C with Python
Solve ABC162 A ~ C with Python
Template AtCoder ABC 179 Python (A ~ E)
Solve ABC167 A ~ C with Python
ABC128 A, B, C commentary (python)
ABC126 A, B, C Explanation (python)
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
Solve ABC169 in Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Solve AtCoder ABC166 with python
[AtCoder explanation] Control the A, B, C problems of ABC182 with Python!
Atcoder ABC164 A-C in Python
ABC129 A, B, C commentary
[AtCoder explanation] Control the A, B, C problems of ABC186 with Python!
Atcoder ABC167 A-D in Python
Solve ABC175 D in Python
[AtCoder explanation] Control the A, B, C problems of ABC185 with Python!
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
AtCoder ABC 182 Python (A ~ D)
[AtCoder explanation] Control the A, B, C problems of ABC187 with Python!
Solve AtCoder ABC 186 with Python
[AtCoder explanation] Control the A, B, C problems of ABC184 with Python!
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
Solve ABC166 A ~ D with Python
Solved AtCoder ABC 114 C-755 with Python3
AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
AtCoder ABC168 A case expression solved in Ruby and Python
AtCoder ABC 174 Python
I wanted to solve ABC159 in Python
Learn dynamic programming in Python (A ~ E)
AtCoder ABC 175 Python
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
What happens if you do "import A, B as C" in Python?
Call a Python script from Embedded Python in C ++ / C ++
I tried adding a Python3 module in C
Daily AtCoder # 36 in Python
Daily AtCoder # 2 in Python