AtCoder Beginner Contest 183の感想

ABC183に参加した。

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – ReLU

ディープラーニングでおなじみReLU。

x = int(input())
ans = max(x, 0)
print(ans)

B – Billiards

反射をそのまま考えると面倒なので、スタート地点をx軸で反転させた( Sx, – Sy )とゴールを結んだ時に交わるx座標を求める、という問題に読み替える。

sx, sy, gx, gy = map(int, input().split())

grad = (sy + gy) / (gx - sx)
ans = sy / grad + sx
print(ans)

C – Travel

N<8なので、総当たりしてもO(8!)=O(10^4)なので間に合う。

現在地を更新しながら移動時間を求めていく。

import itertools

n, k = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]

all = itertools.permutations(range(1, n))

ans = 0
for x in all:
    now = 0
    temp = 0
    for i in x:
        temp += t[now][i]
        now = i
        if temp > k:
            break
    temp += t[now][0]
    if temp == k:
        ans += 1

print(ans)

D – Water Heater

各区間を更新しながら最後に全体の何かを求める、という問題にはいもす法が使える。

いもす方がそのまま使えたのでやるだけ。

n, w = map(int, input().split())
stp = [list(map(int, input().split())) for _ in range(n)]

imos = [0] * (20 ** 5 + 10)

l = 0
r = 0
for s, t, p in stp:
    imos[s] += p
    imos[t] -= p
    l = min(l, s)
    r = max(r, t)

imos = imos[l:r + 10]

for i in range(1, len(imos)):
    imos[i] += imos[i - 1]

print('Yes') if max(imos) <= w else print('No')

毎回D問題まで解いて安定した緑パフォーマンスを出していきたい。