개인 노트

감상

abcd4 완료
녹색이 부족하다

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\leqa\leqb\leq10^9 따라서 직접 설치하면 TLE
따라서 변경된 날짜만 바라보면 1\leqN\leq2\times10^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

해설ac
https://atcoder.jp/contests/abc188/editorial/477
나는 가장 싼 도시에서 사고 가장 비싼 도시에서 팔면 된다는 것을 안다
그래서 어느 도시에서 돈을 사기로 했어요.
한 구역을 제외하고 그곳에서 이동할 수 있는 도시를 전방위적으로 탐색하여 가격이 가장 높은 거리와 가격 차이를 계산해내다
모든 도시부터 이걸 진행하면 돼요.
안 적으면 TLE 되니까 dfs 적어놔야 돼요.
이렇게 되면 큰일난다
다음은 해설해법 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)