AtCoder Beginners Contest Past Question Challenge 10

AtCoder Beginners Contest Past Question Challenge 10

ABC087D - People on a Line

All you have to do is set the position of one of the people associated with the information to 0 and check if there is a contradiction in DFS. Note that it is not always a group.

from sys import stdin

N, M = map(int, stdin.readline().split())

links = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, D = map(int, stdin.readline().split())
    links[L].append((R, D))
    links[R].append((L, -D))

t = [None] * (N + 1)
for i in range(1, N + 1):
    if t[i] is not None:
        continue
    t[i] = 0
    s = [i]
    while s:
        j = s.pop()
        for k, l in links[j]:
            if t[k] is None:
                t[k] = t[j] + l
                s.append(k)
            else:
                if t[k] != t[j] + l:
                    print('No')
                    exit()
print('Yes')

Weighted Union Find Can be solved with a tree.

from sys import setrecursionlimit, stdin


def find(parent, diff_weight, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, diff_weight, t)
    diff_weight[i] += diff_weight[parent[i]]
    parent[i] = t
    return t


def weight(parent, diff_weight, i):
    find(parent, diff_weight, i)
    return diff_weight[i]


def unite(parent, diff_weight, i, j, d):
    d -= weight(parent, diff_weight, j)
    d += weight(parent, diff_weight, i)
    i = find(parent, diff_weight, i)
    j = find(parent, diff_weight, j)
    if i == j:
        return
    diff_weight[j] = d
    parent[i] += parent[j]
    parent[j] = i


setrecursionlimit(10 ** 6)

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

parent = [-1] * (N + 1)
diff_weight = [0] * (N + 1)
for L, R, D in LRD:
    i = find(parent, diff_weight, L)
    j = find(parent, diff_weight, R)
    if i != j:
        unite(parent, diff_weight, L, R, D)
    else:
        if weight(parent, diff_weight, L) + D != weight(parent, diff_weight, R):
            print('No')
            exit()
print('Yes')

ABC136E - Max GCD

No matter how many operations you do, the total does not change, so the only candidate answer is a divisor of the total. After that, you can make it a multiple of that divisor with K operations, but sort the remainder divided by that divisor. If you do, the one that should be subtracted comes to the front, and the one that should be added comes to the back, so if you count in order from the front and back, you can calculate the minimum number of operations required.

def make_divisor_list(n):
    result = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            result.append(i)
            result.append(n // i)
    return result


def calc_min_ops(r, d):
    i, j = 0, len(r)
    while i < j and r[i] == 0:
        i += 1
    i -= 1
    a, b = 0, 0
    while j - i != 1:
        if a <= b:
            i += 1
            a += r[i]
        else:
            j -= 1
            b += d - r[j]
    return a


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

c = sum(A)
divisors = make_divisor_list(c)
divisors.sort(reverse=True)
r = [None] * N

for d in divisors:
    for i in range(N):
        r[i] = A[i] % d
    r.sort()
    if calc_min_ops(r, d) <= K:
        print(d)
        break

ABC063D - Widespread

It may be at least ceil (max (h) / b) or less, but it is too late to calculate the difference between A and B in order from the one with the largest physical strength (confirmed using heapq). When I was told that, it was a wonder that I could solve it in an instant, but I couldn't think of it at all.

from bisect import bisect_right

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

h.sort()
d = A - B

ng = (h[-1] + (A - 1)) // A - 1
ok = (h[-1] + (B - 1)) // B
while ok - ng > 1:
    m = (ok + ng) // 2
    b = B * m
    if m >= sum((h[i] - b + (d - 1)) // d for i in range(bisect_right(h, b), N)):
        ok = m
    else:
        ng = m
print(ok)

ABC060D - Simple Knapsack

I thought that knapsack = DP and thought in that direction, but I can not think of it at all. In the first place, N ≤ 100 and w1 ≤ wi ≤ w1 + 3, so even if I search all (100/4 + 1) 4 </ strong It had to be sup> ≒ 4.6 × 10 5 </ sup>, and it was okay to do a full search.

from sys import stdin
from itertools import accumulate
readline = stdin.readline

N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w, v = map(int, input().split())
w1 = w
vs[0].append(v)
for _ in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = [0] + list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0])):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1])):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2])):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = vs[0][i] + vs[1][j] + vs[2][k]
            for l in range(len(vs[3])):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                result = max(result, t + vs[3][l])
print(result)

ABC122D - We Like AGC

In short, AGC, ACG, GAC, A? GC, AG? C are useless, so you only need to hold the last 3 characters at most. 4 3 </ sup> -3 types, roughly from there Since it is derived four times, the amount of calculation is roughly 250 × 100 = 2.5 × 10 4 </ sup>, which is within the margin range. That is why it was solved by DP.

def is_ok(s):
    if s[1:] in ['AGC', 'ACG', 'GAC']:
        return False
    if s[0] == 'A' and s[2:] == 'GC':
        return False
    if s[:2] == 'AG' and s[3] == 'C':
        return False
    return True


m = 1000000007

N = int(input())

d = {}
for i in 'ACGT':
    for j in 'ACGT':
        for k in 'ACGT':
            d[i + j + k] = 1
for k in ['AGC', 'ACG', 'GAC']:
    del d[k]

for i in range(N - 3):
    t = {}
    for k in d:
        for i in 'ACGT':
            s = k + i
            if is_ok(s):
                t.setdefault(s[1:], 0)
                t[s[1:]] += d[k]
                t[s[1:]] %= m
    d = t

print(sum(d.values()) % m)

ABC100D - Patisserie ABC

I thought it would be easy if there was no absolute value. Then I wondered if I should find the maximum values of plus and minus respectively. That's 2 3 </ sup> times, if there is no absolute value Since it is the same as doing, there is no problem in terms of computational complexity. I was not sure that it would be the maximum value, but it seems that it was an idea because it was AC.

from itertools import product
from sys import stdin
readline = stdin.readline

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

result = 0
for s in product([1, -1], repeat=3):
    xyz.sort(reverse=True, key=lambda e: s[0] * e[0] + s[1] * e[1] + s[2] * e[2])
    cx, cy, cz = 0, 0, 0
    for x, y, z in xyz[:M]:
        cx += x
        cy += y
        cz += z
    result = max(result, abs(cx) + abs(cy) + abs(cz))
print(result)

Recommended Posts

AtCoder Beginners Contest Past Question Challenge 6
AtCoder Beginners Contest Past Question Challenge 4
AtCoder Beginners Contest Past Question Challenge 7
AtCoder Beginners Contest Past Question Challenge 10
AtCoder Beginners Contest Past Question Challenge 5
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Past Question Challenge 1
AtCoder Past Question Review (12 / 6,7)
AtCoder Past Question Review (12/5)
Challenge AtCoder
AtCoder Beginner Contest 066 Review past questions
# 2 Python beginners challenge AtCoder! ABC085C --Otoshidama
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest: D Question Answers Python
AtCoder Beginner Contest 071 Review of past questions