Zenn
💨

[python]ABC183 個人的メモ[AtCoder]

2020/11/16に公開
Python
競技プログラミング
AtCoder
tech

ABC183

所感

abcd4完
緑に復帰した
やったぜ

A - ReLU

ReLU=活性化関数
https://ja.wikipedia.org/wiki/活性化関数

#!/usr/bin/env python3
x = int(input())

print(max(0, x))

B - Billiards

始点のx軸に対して線対称な位置の点から終点に向けて線を引けばおｋ

#!/usr/bin/env python3
sx, sy, gx, gy = map(int, input().split())

print(sx - (sx - gx) / (sy + gy) * sy)

C - Travel

全探索
すべてのパターンが8!=40,320なので十分間に合う
ただし，最初と最後が都市1なことに注意

#!/usr/bin/env python3
from itertools import permutations

N, K = map(int, input().split())
T = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for order in permutations(range(1, N)):
    now = 0
    res = 0
    for i in order:
        res += T[now][i]
        now = i
    res += T[now][0]
    if res == K:
        ans += 1

print(ans)

D - Water Heater

いもす法
https://imoz.jp/algorithms/imos_method.html

#!/usr/bin/env python3
from itertools import accumulate

N, W = map(int, input().split())
time_max = 3 * 10 ** 5
lst = [0] * (time_max)
for _ in range(N):
    s, t, p = map(int, input().split())
    lst[s] += p
    lst[t] -= p
lst = list(accumulate(lst))

if max(lst) <= W:
    print("Yes")
else:
    print("No")

E - Queen on Grid

あるマスの場合の数は漸化式で示せるからdp
各マスごとで連続している縦横斜め方向のマスの場合の数を計算するとTLEするから，それぞれの方向に累積和を持っておく
壁マスは何もせず飛ばせばおｋ

#!/usr/bin/env python3
H, W = map(int, input().split())
S = [input() for _ in range(H)]
MOD = 10 ** 9 + 7

dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
row_cumsum = [[0] * (W + 1) for _ in range(H + 1)]
line_cumsum = [[0] * (W + 1) for _ in range(H + 1)]
slant_cumsum = [[0] * (W + 1) for _ in range(H + 1)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        dp[i][j] += (row_cumsum[i][j - 1]
                     + line_cumsum[i - 1][j]
                     + slant_cumsum[i - 1][j - 1])
        dp[i][j] %= MOD

        row_cumsum[i][j] = dp[i][j] + row_cumsum[i][j - 1]
        row_cumsum[i][j] %= MOD
        line_cumsum[i][j] = dp[i][j] + line_cumsum[i - 1][j]
        line_cumsum[i][j] %= MOD
        slant_cumsum[i][j] = dp[i][j] + slant_cumsum[i - 1][j - 1]
        slant_cumsum[i][j] %= MOD

print(dp[-1][-1])

参考

Discussion