AtCoder Beginner Contest 188 Participation Report

AtCoder Beginner Contest 188 Participation Report

ABC188A - Three-Point Shot

Break through in 2 minutes. Just write.

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

if Y < X:
    X, Y = Y, X

if X + 3 > Y:
    print('Yes')
else:
    print('No')

ABC188B - Orthogonality

Break through in 2 minutes. Just write.

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

if sum(a * b for a, b in zip(A, B)) == 0:
    print('Yes')
else:
    print('No')

ABC188C - ABC Tournament

Break through in 7 minutes. N ≤ 16, so even if you run the tournament obediently, it will not TLE with * O * (2 17 ), so do it obediently AC.

N, *A = map(int, open(0).read().split())

a = range(2 ** N)
while len(a) != 2:
    t = []
    for i in range(0, len(a), 2):
        if A[a[i]] > A[a[i + 1]]:
            t.append(a[i])
        else:
            t.append(a[i + 1])
    a = t
if A[a[0]] > A[a[1]]:
    print(a[1] + 1)
else:
    print(a[0] + 1)

After the contest, I divided the mountain into two in the middle and realized that the strongest one on the side without the strongest one was the runner-up, so I couldn't solve it quickly.

N, *A = map(int, open(0).read().split())

i = A.index(max(A))
if i < 2 ** (N - 1):
    print(A.index(max(A[:2 ** (N - 1)]) + 1)
else:
    print(A.index(max(A[2 ** (N - 1):]) + 1)

ABC188D - Snuke Prime

It broke through in 13 minutes. The moment I saw the problem statement, I thought I was lucky to have one imos method, but I was indignant when I saw b i ≤ 10 9 . I was surprised to find that there was no problem when I simulated the method in my brain. AC. It seems that sitting pressure was fine. Let's solve it later.

from sys import stdin

readline = stdin .readline

N, C = map(int, readline().split())

d = {}
for _ in range(N):
    a, b, c = map(int, readline().split())
    d.setdefault(a, 0)
    d[a] += c
    d.setdefault(b + 1, 0)
    d[b + 1] -= c

skeys = sorted(d)
for i in range(1, len(skeys)):
    d[skeys[i]] += d[skeys[i - 1]]
for k in d:
    if d[k] > C:
        d[k] = C

result = 0
for i in range(len(skeys) - 1):
    result += d[skeys[i]] * (skeys[i + 1] - skeys[i])
print(result)

Postscript: I tried to solve it by coordinate compression + imos method.

from sys import stdin
from itertools import accumulate

readline = stdin .readline

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

p = set()
for a, b, _ in abc:
    p.add(a)
    p.add(b)
    p.add(b + 1)
inv = sorted(p)
fwd = {}
for i in range(len(inv)):
    fwd[inv[i]] = i

t = [0] * len(inv)
for a, b, c in abc:
    t[fwd[a]] += c
    t[fwd[b + 1]] -= c
t = list(accumulate(t))

result = 0
for i in range(len(t) - 1):
    result += min(t[i], C) * (inv[i + 1] - inv[i])
print(result)

Postscript: I tried to solve it by the method described in the commentary. Hmm, smart.

from sys import stdin

readline = stdin .readline

N, C = map(int, readline().split())

q = []
for _ in range(N):
    a, b, c = map(int, readline().split())
    q.append((a, c))
    q.append((b + 1, -c))

result = 0
p = 0
ac = 0
for x, y in sorted(q):
    result += min(C, ac) * (x - p)
    p = x
    ac += y
print(result)

ABC188E - Peddler

Break through in 67 minutes. WA2. The moment I read the problem statement, I knew that I should do it from behind, but for some reason I used Union Find to manage it and self-destructed.

from sys import stdin

readline = stdin.readline

N, M = map(int, readline().split())
A = list(map(int, readline().split()))

links = [[] for _ in range(N)]
for _ in range(M):
    X, Y = map(lambda x: int(x) - 1, readline().split())
    links[X].append(Y)

maxvs = [None] * N
result = -(10 ** 18)
for i in range(N - 1, -1, -1):
    if len(links[i]) == 0:
        maxvs[i] = A[i]
        continue
    maxv = max(maxvs[j] for j in links[i])
    result = max(result, maxv - A[i])
    maxvs[i] = max(maxv, A[i])
print(result)

Postscript: It was okay to do it from before, and I feel that this is easier to understand.

from sys import setrecursionlimit, stdin
from functools import lru_cache

setrecursionlimit(10 ** 6)
readline = stdin.readline

N, M = map(int, readline().split())
A = list(map(int, readline().split()))

links = [[] for _ in range(N)]
for _ in range(M):
    X, Y = map(lambda x: int(x) - 1, readline().split())
    links[X].append(Y)


@lru_cache(maxsize=None)
def dfs(x):
    result = A[x]
    for y in links[x]:
        result = max(result, dfs(y))
    return result


result = -(10 ** 18)
for i in range(N):
    if len(links[i]) == 0:
        continue
    result = max(result, max(dfs(j) for j in links[i]) - A[i])
print(result)

ABC188F - +1-1x2

I went to WA2 but couldn't break through. Should I have done it with memoization recursion instead of Greedy? (Y-1) ÷ 2 was prioritized, but (Y + 1) ÷ 2 was sometimes better. It seems. I knew by doing a similar problem somewhere that it was better to change Y instead of changing X.

from functools import lru_cache

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


@lru_cache(maxsize=None)
def f(y):
    if X >= y:
        return abs(X - y)
    if y % 2 == 0:
        return min(abs(y - X), f(y // 2) + 1)
    else:
        return min(abs(y - X), f((y - 1) // 2) + 2, f((y + 1) // 2) + 2)


print(f(Y))

Recommended Posts

AtCoder Beginner Contest 161 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 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 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 182 Participation Report
AtCoder Beginner Contest 152 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 Beginner Contest 146 Participation Diary
AtCoder Chokudai Contest 005 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 177
AtCoder Beginner Contest 172
AtCoder Beginner Contest 173
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing 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 187 Note
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 166 Review
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 171 Review