[PYTHON] AtCoder Débutant Contest 157 Rapport de participation

AtCoder Débutant Contest 157 Rapport de participation

ABC157A - Duplex Printing

Percer en 1 minute. Il suffit d'écrire.

N = int(input())

print((N + 1) // 2)

ABC157B - Bingo

Percer en 7 minutes et demie. Il suffit d'écrire ... mais comment écrire si je veux écrire avec élégance ... Surtout au jugement du bingo.

A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())

for _ in range(N):
    b = int(input())
    for y in range(3):
        for x in range(3):
            if A[y][x] == b:
                A[y][x] = -1

for y in range(3):
    f = True
    for x in range(3):
        if A[y][x] != -1:
            f = False
    if f:
        print('Yes')
        exit()

for x in range(3):
    f = True
    for y in range(3):
        if A[y][x] != -1:
            f = False
    if f:
        print('Yes')
        exit()

f = True
for x in range(3):
    if A[x][x] != -1:
        f = False
if f:
    print('Yes')
    exit()

f = True
for x in range(3):
    if A[2 - x][x] != -1:
        f = False
if f:
    print('Yes')
    exit()

print('No')

ABC157C - Guess The Number

Percer en 20 minutes. WA4. Hmm, c'est terrible. Quand N = 1, j'ai oublié le fait que le premier chiffre peut être pris et il est devenu grumeleux. À part cela, ce n'est pas difficile à résoudre, et les chiffres déterminés par le tableau Tout ce que vous avez à faire est de gérer et d'attribuer le plus petit nombre aux chiffres indécis.

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

t = [-1] * N
for _ in range(M):
    s, c = map(int, input().split())
    s -= 1
    if t[s] != -1 and t[s] != c:
        print(-1)
        exit()
    t[s] = c

if N != 1:
    if t[0] == 0:
        print(-1)
        exit()

    if t[0] == -1:
        t[0] = 1

    for i in range(1, N):
        if t[i] == -1:
            t[i] = 0
else:
    if t[0] == -1:
        t[0] = 0

print(''.join(map(str, t)))

ABC157D - Friend Suggestions

Je ne sais pas exactement parce que j'ai fait un détour par E. Les candidats amis ont la taille du groupe d'amis de mon ami moins les suivants.

--Mon numéro (= 1) --Nombre d'amis --Nombre de personnes bloquées dans le groupe d'amis de votre ami

La taille du groupe d'amis de votre ami peut être facilement déterminée avec la taille UnionFind.

from sys import setrecursionlimit


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


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


setrecursionlimit(10 ** 5)


N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

parent = [-1] * N
friends = [[] for _ in range(N)]
for A, B in AB:
    unite(parent, A - 1, B - 1)
    friends[A-1].append(B-1)
    friends[B-1].append(A-1)
blocks = [[] for _ in range(N)]
for C, D in CD:
    blocks[C-1].append(D-1)
    blocks[D-1].append(C-1)

result = []
for i in range(N):
    p = find(parent, i)
    t = -parent[p] - 1
    t -= len(friends[i])
    for b in blocks[i]:
        if p == find(parent, b):
            t -= 1
    result.append(t)
print(*result)

ABC157E - Simple String Queries

Perdu. Je me suis demandé si je pouvais utiliser l'arborescence Seg et le set, mais TLE. Je me suis demandé si je pouvais utiliser l'arborescence Seg retardée, donc je n'ai pas eu le temps d'enquêter correctement, j'ai donc écrit de manière appropriée que je devrais gérer Dirty, mais les performances se sont améliorées Mais TLE ne disparaît pas. PyPy a encore amélioré les performances, mais ce n'est toujours pas suffisant.

Addendum: Quand j'ai arrêté de définir et que je l'ai exprimé en bit, ça a passé facilement. Puisque le type de caractère n'est que minuscule, je peux l'exprimer avec 26 bits. Pourquoi ne clignote-t-il pas pendant le concours (soupir).

class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0 for _ in range(t * 2 - 1)]

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = [1 << (ord(c) - ord('a')) for c in iterable]
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = 1 << (ord(value) - ord('a'))
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def query(self, start, stop):
        result = 0
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = result | self._data[l]
            if r & 1 == 0:
                result = result | self._data[r - 1]
            l = l // 2
            r = (r - 1) // 2
        return result


N = int(input())
S = input()

st = SegmentTree(N)
st.update_all(S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, c)
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(bin(st.query(l - 1, r)).count('1'))