AtCoder ABC187 個人的メモ

3 min read読了の目安(約3300字

所感

abcd4完
緑復帰
abc187score

A - Large Digits

A, B = input().split()

a = 0
b = 0
for i in A:
    a += int(i)
for i in B:
    b += int(i)

if a >= b:
    print(a)
else:
    print(b)

B - Gentle Pairs

割り算してるので誤差が心配だったけどacした
公式解説の様に移項して割り算しない不等式にした方が良い
https://atcoder.jp/contests/abc187/editorial/484

from itertools import combinations

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

ans = 0
for a, b in combinations(pnts, 2):
    res = (b[1] - a[1]) / (b[0] - a[0])
    if -1 <= res <= 1:
        ans += 1

print(ans)

C - 1-SAT

先頭に!のある!を除いた文字列と,先頭に!の無い文字列で2つの集合を作る
両方の集合にに含まれる文字列を出力すればおk

N = int(input())

zero_set = set()
one_set = set()
for _ in range(N):
    s = input()
    if s[0] == "!":
        one_set.add(s[1:])
    else:
        zero_set.add(s)

ans = "satisfiable"
for i in zero_set:
    if i in one_set:
        ans = i

print(ans)

D - Choose Me

https://atcoder.jp/contests/abc187/editorial/486

N = int(input())
score = 0
speach = []
for _ in range(N):
    a, b = map(int, input().split())
    score -= a
    speach.append((a * 2 + b))

ans = 0
speach.sort(reverse=True)
for i in speach:
    score += i
    ans += 1
    if score > 0:
        break

print(ans)

E - Through Path

解説ac
https://atcoder.jp/contests/abc187/editorial/487

tと頂点a,bのどちらが親かで以下の様に場合分けできる

  • t=1かつaが親
    aaの先祖全てにxを足す
    又は,bbの子孫全てに-xを足し,木全体(根と根の子孫)にxを足す

  • t=1かつbが親
    aaの子孫全てにxを足す

  • t=2かつaが親
    bbの子孫全てにxを足す

  • t=2かつbが親
    bbの先祖全てにxを足す
    又は,aaの子孫全てに-xを足し,木全体(根と根の子孫)にxを足す

これらの操作は各頂点にのみxを足しておけば,根から累積和をとっていくことで後からまとめて計算できる
これで,各クエリでの操作はO(1)で済む

従って.以下の手順で実装すればおk
各頂点番号は0-indexとして,根は0とした

  1. 木を作る
  2. 2頂点間の高さを比較するために,木の各頂点の高さを調べる
  3. クエリ処理
  4. 累積和
from collections import deque

N = int(input())
edge = []
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)

# 2頂点a,bのどちらが親かを判定するために各頂点の高さを調べておく
queue = deque([0])
depth = [-1] * N
depth[0] = 0
while queue:
    now = queue.popleft()
    for i in graph[now]:
        if depth[i] != -1:
            continue
        depth[i] = depth[now] + 1
        queue.append(i)

node_num = [0] * N
Q = int(input())
for _ in range(Q):
    t, e, x = map(int, input().split())
    a, b = edge[e - 1]
    if t == 1:
        if depth[a] < depth[b]:
            node_num[b] -= x
            node_num[0] += x
        else:
            node_num[a] += x
    else:
        if depth[a] < depth[b]:
            node_num[b] += x
        else:
            node_num[a] -= x
            node_num[0] += x

queue = deque([0])
while queue:
    now = queue.popleft()
    for i in graph[now]:
        if depth[i] < depth[now]:
            continue
        node_num[i] += node_num[now]
        queue.append(i)

print(*node_num, sep="\n")