AtCoder ABC188 個人的メモ

所感

abcd4完
緑に1足りない

A - Three-Point Shot

X, Y = map(int, input().split())

if abs(X - Y) < 3:
    print("Yes")
else:
    print("No")

B - Orthogonality

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in range(N):
    ans += A[i] * B[i]

if ans == 0:
    print("Yes")
else:
    print("No")

C - ABC Tournament

公式解説解法2は賢いなぁって思った
https://atcoder.jp/contests/abc188/editorial/481

N = int(input())
A = list(map(int, input().split()))
 
lst = []
for i in range(2 ** N):
    lst.append((A[i], i + 1))
 
while len(lst) > 2:
    winner = []
    for i in range(0, len(lst), 2):
        if lst[i][0] >= lst[i + 1][0]:
            winner.append(lst[i])
        else:
            winner.append(lst[i + 1])
    lst = winner
 
if lst[0][0] <= lst[1][0]:
    print(lst[0][1])
else:
    print(lst[1][1])

# 公式解説解法2
N = int(input())
lst = [(x, i + 1) for i, x in enumerate(map(int, input().split()))]

champion_index = max(lst)[1]
res = 2 ** (N - 1)
if champion_index > res:
    print(max(lst[:res])[1])
else:
    print(max(lst[res:])[1])

D - Snuke Prime

大体想定解法を少し雑にしたような解答

いもす法を使えば良さそうってのは分かった
でも，$1\leq a\leq b\leq 10^9$なので素直に実装するとTLEしそう
なので，変化が起きる日にちだけに注目すれば$1\leq N\leq 2\times 10^5$なので間に合いそう

from heapq import heappop

N, C = map(int, input().split())
plan = []
for i in range(N):
    a, b, c = map(int, input().split())
    b += 1
    plan.append((a, c))
    plan.append((b, -c))

plan.sort()
fee = 0
last_day = 1
ans = 0
while plan:
    day, cost = heappop(plan)
    res = min(fee, C)
    ans += res * (day - last_day)
    fee += cost
    while plan and plan[0][0] == day:
        x, y = heappop(plan)
        fee += y
    last_day = day

print(ans)

E - Peddler

解法2で解説ac
https://atcoder.jp/contests/abc188/editorial/477

一番安い町で買って，一番高い町で売れば良いのは分かる
なので，ある町で金を買うとする
ある街を除いた，そこから移動できる町を全探索して価格が最も高い街との価格差を計算する
これを全ての町から行えば良い
メモ化しないとTLEするのでdfsをメモ化する
こうやったらwaした

下のは解説の解法2の通り実装したもの
↑のとは違い，値段の安い街からbfsで探索
要復習

from collections import deque

INF = 10 ** 18
N, M = map(int, input().split())
A = [-INF] + list(map(int, input().split()))
cost = [(A[i], i) for i in range(1, N + 1)]
G = [[] for _ in range(N + 1)]
for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)

# bfs
cost.sort()
cost = deque(cost)
ans = -INF
seen = [False] * (N + 1)
while cost:
    yen, root = cost.popleft()
    queue = deque(G[root])
    most_high_price = -INF
    while queue:
        now = queue.popleft()
        if seen[now]:
            continue
        seen[now] = True
        most_high_price = max(most_high_price, A[now])
        for move in G[now]:
            if seen[move]:
                continue
            queue.append(move)
    ans = max(ans, most_high_price - yen)

print(ans)