AtCoder ABC187 個人的メモ

所感

abcd4完
緑復帰

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つの集合を作る
両方の集合にに含まれる文字列を出力すればおｋ

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$が親
  $a$と$a$の先祖全てに$x$を足す
  又は，$b$と$b$の子孫全てに$-x$を足し，木全体(根と根の子孫)に$x$を足す

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

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

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

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

従って．以下の手順で実装すればおｋ
各頂点番号は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")