Concours AtCoder pour débutants Défi des questions passées 10

Concours AtCoder pour débutants Défi des questions passées 10

ABC087D - People on a Line

Tout ce que vous avez à faire est de définir la position de l'une des personnes associées aux informations sur 0 et de vérifier s'il y a une incohérence dans DFS. Notez qu'il ne s'agit pas toujours d'un groupe.

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')

Recherche d'union pondérée Peut être résolue avec un arbre.

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

Quel que soit le nombre d'opérations que vous effectuez, le total ne change pas, donc la seule réponse possible est une fraction du total. Après cela, vous pouvez en faire un multiple de cette fraction avec K opérations, mais trier le reste divisé par cette fraction. Si vous le faites, celui qui doit être soustrait vient à l'avant, et celui qui doit être ajouté vient à l'arrière, donc si vous comptez dans l'ordre de l'avant et de l'arrière, vous pouvez calculer le nombre minimum d'opérations requises.

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

Au moins ceil (max (h) / b) ou moins, mais il est trop tard pour calculer la différence entre A et B dans l'ordre de celui avec la force physique la plus élevée (confirmé à l'aide de heapq). Quand on m'a dit cela, c'était une merveille que je puisse le résoudre en un instant, mais je ne pouvais pas du tout y penser.

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

Je pensais que sac à dos = DP et je pensais dans cette direction, mais je n'y pense pas du tout. En premier lieu, N ≤ 100 et w1 ≤ wi ≤ w1 + 3, donc même si je recherche tout (100/4 + 1) 4 </ strong> Il devait être sup> ≒ 4,6 × 10 5 </ sup>, et il était normal de faire une recherche complète.

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

Bref, AGC, ACG, GAC, A? GC, AG? C sont inutiles, il vous suffit donc de ne garder que les 3 derniers caractères au maximum.4 3 </ sup> -3 Vous n'avez qu'à tenir 3 types, à peu près à partir de là Puisqu'il est dérivé quatre fois, le montant du calcul était d'environ 250 × 100 = 2,5 × 10 4 </ sup>, ce qui était dans la plage de marge. C'est pourquoi il a été résolu par 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

Je pensais que ce serait facile s'il n'y avait pas de valeur absolue. Ensuite, je me suis demandé si je devais trouver les valeurs maximales de plus et moins respectivement. Si tel est le cas, 2 fois 3 </ sup>, s'il n'y a pas de valeur absolue Il n'y a pas de problème en termes de quantité de calcul car c'est la même chose que faire, je n'étais pas sûr que ce serait la valeur maximale, mais il semble que c'était une façon de penser parce que c'était 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

Concours AtCoder pour débutants Défi des questions passées 6
Concours AtCoder pour débutants Défi des questions passées 4
Concours AtCoder pour débutants Défi des questions passées 7
Concours AtCoder pour débutants Défi des questions passées 10
Concours AtCoder Débutants Défi des questions passées 5
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Défi des questions passées 1
Examen des questions passées d'AtCoder (12 / 6,7)
Examen des questions passées d'AtCoder (12/5)
Défiez AtCoder
AtCoder Beginner Contest 066 Revoir les questions précédentes
# 2 Les débutants en Python défient AtCoder! ABC085C --Otoshidama
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
Concours pour débutants AtCoder: Réponses aux problèmes D Python
AtCoder Beginner Contest 071 Revue des questions précédentes