AtCoder Beginner Contest 188の感想

AtCoder

2021.01.112021.03.16

ABC188に参加した。

AtCoder Beginner Contest 188 - AtCoder

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

A – Three-Point Shot

やるだけ。

x, y = map(int, input().split())

ans = min(x, y) + 3 > max(x, y)
print('Yes') if ans else print('No')

B – Orthogonality

問題文の英語は直行性という意味。

制約が緩いので愚直にループ。

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0
for i, j in zip(a, b):
    ans += i * j

print('Yes') if ans == 0 else print('No')

C – ABC Tournament

トーナメントで勝ち残る人を格納する配列を別途用意し、準決勝になるまで（配列の要素数が2になるまで）ループ。

n = int(input())
a = list(map(int, input().split()))

next = a.copy()
while len(next) > 2:
    temp = []
    for i in range(len(next) // 2):
        temp.append(max(next[2 * i], next[2 * i + 1]))
    next = temp

ans = a.index(min(next)) + 1
print(ans)

D – Snuke Prime

本番中はいもす法かと思ったが、制約が1<=Ai<=Bi<=10^9と大きく、メモリの要求量が大きかったので解けなかった。

コンテスト後の解説を見て、支払金額の変動のみに着目することで計算量をO(N logN)に落とせることがわかった。

n, c = map(int, input().split())

event = []
for _ in range(n):
    a, b, q = map(int, input().split())
    event.append([a - 1, q])
    event.append([b, -q])

event.sort()

ans = 0
fee = 0
time = 0

for x, y in event:
    if x != time:
        ans += min(c, fee) * (x - time)
        time = x
    fee += y

print(ans)

また大きな値を扱う時に座標圧縮という手段があるということを初めて知り、座標圧縮後ならいもす法で解くことが出来た。

n, x = map(int, input().split())

event = []
service = []
for _ in range(n):
    a, b, v = map(int, input().split())
    a -= 1
    event.append(a)
    event.append(b)
    service.append([a, b, v])

event.sort()
compress = {a: i for i, a in enumerate(event)}

imos = [0] * len(event)
for a, b, c in service:
    imos[compress[a]] += c
    imos[compress[b]] -= c

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

ans = 0
for i in range(len(imos) - 1):
    diff = event[i + 1] - event[i]
    ans += min(x, imos[i]) * diff

print(ans)

3完早解きでパフォーマンスを維持。