AtCoder Beginner Contest 187 Participation Report

AtCoder Beginner Contest 187 Participation Report

ABC187A - Large Digits

Break through in 2 minutes. Just write.

def S(n):
    return sum(int(c) for c in str(n))


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

print(max(S(A), S(B)))

ABC187B - Gentle Pairs

Break through in 4 and a half minutes. As usual, I started by googled the equation of a straight line passing through two points. I thought it would be bad if I divided it, but it's a B problem and it's safe to read it rotten.

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

result = 0
for i in range(N):
    for j in range(i + 1, N):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        if x1 == x2:
            continue
        a = (y2 - y1) / (x2 - x1)
        if abs(a) <= 1:
            result += 1
print(result)

Postscript: x2 --x1 could not be 0 because of the limitation …….

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

result = 0
for i in range(N):
    x1, y1 = xy[i]
    for j in range(i + 1, N):
        x2, y2 = xy[j]
        if abs(y2 - y1) <= abs(x2 - x1):
            result += 1
print(result)

ABC187C - 1-SAT

Break through in 5 and a half minutes.After writing without looking at the restrictions, I thought for a moment that it would be impossible to do this, but|Si|Since it was ≤10, it became "Oh, it's okay" and AC.

from sys import stdin

readline = stdin.readline

N = int(readline())
S = [readline()[:-1] for _ in range(N)]

t = set()
for s in S:
    if s[0] == '!':
        if s[1:] in t:
            print(s[1:])
            break
        t.add(s)
    else:
        if '!' + s in t:
            print(s)
            break
        t.add(s)
else:
    print('satisfiable')

ABC187D - Choose Me

Break through in 13 minutes. I didn't understand at all for a moment, but when I started with "Sum (A i ) vs 0" and gave a speech in the town j , "Sum (A <A <" sub> i ) --A j vs A j + B j ", so if you transfer it to" Sum (A <A < sub> i ) vs 2A j + B j ". So," 2A j + B j I found that I should make a sequence of "", sort it in descending order, and add it in order, and it became * O * ( N log N ). So I solved it with this.

from sys import stdin

readline = stdin.readline

N = int(readline())
AB = [tuple(map(int, readline().split())) for _ in range(N)]

s = sum(a for a, _ in AB)
t = [a * 2 + b for a, b in AB]
t.sort(reverse=True)

c = 0
for i in range(N):
    c += t[i]
    if c > s:
        print(i + 1)
        break

ABC187E - Through Path

I couldn't break through. I was able to solve it by myself in 21 minutes and 20 seconds from the end of the contest (96 minutes and a half). In my brain, apex a e i and apex b < I rewrote the problem that sub> e i was not adjacent and self-destructed. The method of reducing the amount of calculation is the same as ABC138D --Ki and added to the parent node. I thought it would be good to include it and add it up at the end. Considering that it matches Tsuji, if the trace source is the parent, + x to the root vertex, -x to the blocking vertex, and the trace source is the child. In that case, you can + x to the vertex of the trace source. After that, you can decide which one is the parent, traverse from there and put the parent information in the array with * O * (1). It can be processed. It doesn't matter which vertex is rooted, so I calculated with vertex 1 as the root.

from sys import stdin
from collections import deque

readline = stdin.readline

N = int(readline())
ab = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(N - 1)]

links = [[] for _ in range(N)]
for a, b in ab:
    links[a].append(b)
    links[b].append(a)

parent = [-1] * N
parent[0] = 0
q = deque([0])
while q:
    i = q.popleft()
    for j in links[i]:
        if parent[j] != -1:
            continue
        parent[j] = i
        q.append(j)

c = [0] * N
Q = int(readline())
for _ in range(Q):
    t, e, x = map(int, readline().split())
    a, b = ab[e - 1]
    if t == 2:
        a, b = b, a
    if a == parent[b]:
        c[0] += x
        c[b] -= x
    else:
        c[a] += x

q = deque([0])
while q:
    i = q.popleft()
    for j in links[i]:
        if j == parent[i]:
            continue
        c[j] += c[i]
        q.append(j)

print(*c, sep='\n')

Postscript: Many people have depth information instead of parent information.

from sys import stdin
from collections import deque

readline = stdin.readline

N = int(readline())
ab = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(N - 1)]

links = [[] for _ in range(N)]
for a, b in ab:
    links[a].append(b)
    links[b].append(a)

depth = [-1] * N
depth[0] = 0
q = deque([0])
while q:
    i = q.popleft()
    for j in links[i]:
        if depth[j] != -1:
            continue
        depth[j] = depth[i] + 1
        q.append(j)

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

q = deque([0])
while q:
    i = q.popleft()
    for j in links[i]:
        if depth[j] < depth[i]:
            continue
        c[j] += c[i]
        q.append(j)

print(*c, sep='\n')

Recommended Posts

AtCoder Beginner Contest 181 Participation Report
AtCoder Beginner Contest 151 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Beginner Contest 154 Participation Report
AtCoder Beginner Contest 166 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 165 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Beginner Contest 156 Participation Report
AtCoder Beginner Contest 162 Participation Report
AtCoder Beginner Contest 157 Participation Report
AtCoder Beginner Contest 167 Participation Report
AtCoder Beginner Contest 179 Participation Report
AtCoder Beginner Contest 182 Participation Report
AtCoder Beginner Contest 146 Participation Report
AtCoder Beginner Contest 155 Participation Report
AtCoder Beginner Contest 174 Participation Report
AtCoder Beginner Contest 171 Participation Report
AtCoder Beginner Contest 149 Participation Report
AtCoder Beginner Contest 148 Participation Report
AtCoder Beginner Contest 188 Participation Report
AtCoder Beginner Contest 170 Participation Report
AtCoder Beginner Contest 187 Participation Report
AtCoder Beginner Contest 183 Participation Report
AtCoder Beginner Contest # 003 Participation Note
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Regular Contest 105 Participation Report
AtCoder Regular Contest 104 Participation Report
ACL Beginner Contest Participation Report
AtCoder Chokudai Contest 005 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Panasonic Programming Contest 2020 Participation Report
AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 181 Note
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 167 Review
AtCoder Library Practice Contest Participation Report (Python)
AtCoder Beginner Contest 182 Note
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review