Concours AtCoder Débutants Défi des questions passées 5

Concours AtCoder Débutants Défi des questions passées 5

ABC134D - Preparing Boxes

Il n'y a rien de particulièrement difficile si vous décidez dans l'ordre en diminuant i de i = N.

N = int(input())
a = list(map(int, input().split()))

t = [0] * N
for i in range(N - 1, -1, -1):
    t[i] = (sum(t[2 * (i + 1) - 1::i + 1]) % 2) ^ a[i]

print(sum(t))
print(*[i + 1 for i in range(N) if t[i] == 1])

ABC080D - Recording

À première vue, il semble que la méthode imos est un coup, mais comme il y a S -0,5, si vous utilisez la méthode imos sans penser à rien, le nombre d'enregistrements consécutifs sur le même canal ne sera de deux que pendant 0,5.

La solution la plus simple est de quitter la méthode imos. Si = 1 au lieu de + = 1, il est possible de doubler, et en fait, c'est correct en termes de temps de traitement.

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

tt = [[0] * (10 ** 5 + 1) for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    for i in range(s - 1, t):
        tt[c - 1][i] = 1

ct = [0] * (10 ** 5 + 1)
for i in range(C):
    for j in range(10 ** 5 + 1):
        ct[j] += tt[i][j]

print(max(ct))

Ce n'est pas difficile à faire avec la méthode imos, mais c'est étonnamment difficile à écrire avec élégance. Est-il plus facile de trier et de modifier le mouvement s'il est continu?

from operator import itemgetter

N, C = map(int, input().split())
stc = [list(map(int, input().split())) for _ in range(N)]
stc.sort(key=itemgetter(2, 0))

cs = [0] * (10 ** 5 + 1)
pt, pc = -1, -1
for s, t, c in stc:
    if pt == s and pc == c:
        cs[s] += 1
    else:
        cs[s - 1] += 1
    cs[t] -= 1
    pt, pc = t, c

for i in range(1, 10 ** 5 + 1):
    cs[i] += cs[i - 1]

print(max(cs))

Au fait, en théorie, cela peut être de la mousse, mais si je passais par le canal qui ne toucherait pas autant, j'ai été snipé fermement.

ABC121D - XOR World

Puisque f (A, B) est identique à f (0, A-1) xor f (0, B), g (N) = f (0, N) Il suffit de l'écrire. Vous pouvez compter le nombre de 1 pour chaque chiffre du nombre binaire et le traiter comme pair ou impair.

def h(A, n):
    if A == -1:
        return 0
    return A // (2 * n) * n + max(A % (2 * n) - (n - 1), 0)


def g(A):
    result = 0
    for i in range(48):
        t = 1 << i
        if h(A, t) % 2 == 1:
            result += t
    return result


def f(A, B):
    return g(A - 1) ^ g(B)


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

print(f(A, B))

En fait, pour tout n pair, n xor (n + 1) ʻest 1`, vous n'avez donc pas à compter pour chaque chiffre.

def g(A):
    t = ((A + 1) // 2) % 2  #Pour tout même n n^ (n + 1) == 1
    if A % 2 == 0:
        return A ^ t
    return t


def f(A, B):
    return g(A - 1) ^ g(B)


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

print(f(A, B))

ABC117D - XXOR

Pour chaque bit de A, additionnez le nombre de bits debout et non debout, et si le nombre de bits debout est plus grand, le bit est 0, et si le nombre de bits non debout est plus grand, le bit est 1 X. Cependant, comme X a une condition de K ou moins, si elle dépasse K, je renoncerai un peu à régler.

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

bcs = [0] * 41
for i in range(N):
    a = A[i]
    for j in range(41):
        if a & (1 << j) != 0:
            bcs[j] += 1

X = 0
for i in range(40, -1, -1):
    if bcs[i] >= N - bcs[i]:
        continue
    t = 1 << i
    if X + t <= K:
        X += t

result = 0
for i in range(N):
    result += X ^ A[i]
print(result)

ABC094D - Binomial Coefficients

a i </ sub> est le nombre maximum. A j </ sub> est le prochain plus grand nombre, mais a i </ sub> </ sub> C < sub> a j </ sub> </ sub> == a i </ sub> </ sub> C a i </ sub> -a j </ sub> </ sub> et recherchez l'ordre.

n = int(input())
a = list(map(int, input().split()))

a.sort()
x = a[-1]
b = [(min(e, x - e), e) for e in a[:-1]]
b.sort()
print(x, b[-1][1])

ABC098D - Xor Sum 2

L'addition est une augmentation monotone, mais XOR n'est pas une augmentation monotone car 1 xor 1 est égal à 0. En passant, puisque 0 xor N == 0 + N, "XOR <= addition". Alors, peu importe combien vous augmentez le nombre de r à partir de là, ce ne sera pas toujours le même. De plus, si un certain l <r a la même valeur, la combinaison de l + 1 et r aura également la même valeur. Vous pouvez voir que la méthode Toshakutori est bonne.

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

result = 0
r = 0
xs = A[0]
cs = A[0]
for l in range(N):
    while r < N - 1 and xs ^ A[r + 1] == cs + A[r + 1]:
        r += 1
        xs ^= A[r]
        cs += A[r]
    result += r - l + 1
    xs ^= A[l]
    cs -= A[l]
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 9
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
# 2 Les débutants en Python défient AtCoder! ABC085C --Otoshidama
AtCoder Beginner Contest 102 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 051 Revue des questions précédentes
AtCoder Beginner Contest 119 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 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 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 083 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 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 094 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
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes