Atcoder ABC176 (A,B,C,E)をPythonで解く

テスト中解けたのはA,B,Cの3問。D,Eはコンテスト中はTLEでした。

A - Takoyaki

コメント：特になし

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

コメント：特になし（Aより簡単・・？）

N = int(input())

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

C - Step

コメント：特になし

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

コメント：幅優先探索か深さ優先探索かどちらを使えばいいかがわからず、
とりあえず実装が楽な深さ優先探索を使ってみたがTLE。
解説を見たところ、幅優先探索で解くみたいなので、時間があるときに
幅優先探索で解きなおす。

# 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

コメント：解き方は単純だったが、コンテスト中はlistで実装していたため、TLEになった。
listとset,tupleの速度面での使い分けをこれまで意識していなかったので、今後は気を付ける。

TLEと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))

全体コード

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)