AtCoder 2nd Algorithm Practical Test Virtual Participation Report

AtCoder 2nd Algorithm Practical Test Virtual Participation Report

Le résultat était de 76 points, ce qui était intermédiaire (60-79 points). La dernière fois, j'étais à peine intermédiaire avec 64 points, mais cette fois j'étais avancé si je résolvais encore une question.

past202004A --Elevator

Si vous définissez Bx sur -x et xF sur x, vous devez seulement faire attention lorsque la différence entre B1 et 1F n'est pas 1.

S, T = input().split()


def f(s):
    if s[0] == 'B':
        return -int(s[1])
    else:
        return int(s[0]) - 1


print(abs(f(S) - f(T)))

past202004B --Décision majoritaire

Percer en 3 minutes et demie. Il suffit de regrouper et de produire le plus.

S = input()

d ={}
for c in S:
    d.setdefault(c, 0)
    d[c] += 1
print(sorted(((d[k], k) for k in d), reverse=True)[0][1])

passé202004 C - Effondrement de la montagne

Pénétrez en 12 minutes. Écrivez simplement en fonction de l'énoncé du problème.

N = int(input())
S = [input() for _ in range(N)]

T = [list(l) for l in S]
for i in range(N - 2, -1, -1):
    for j in range(2 * N - 1):
        if T[i][j] == '.':
            continue
        if j - 1 >= 0:
            if T[i + 1][j - 1] == 'X':
                T[i][j] = 'X'
        if T[i + 1][j] == 'X':
            T[i][j] = 'X'
        if j + 1 < 2 * N - 1:
            if T[i + 1][j + 1] == 'X':
                T[i][j] = 'X'
for l in T:
    print(''.join(l))

passé202004D --Mattern match

Percer en 11 minutes. Puisque "." Est un caractère arbitraire, c'est une expression régulière à faire correspondre. Après cela, tous les modèles sont générés, mais Python est itertools.product.

from itertools import product
from re import search

S = input()

cs = set(S)
cs.add('.')

result = 0
for i in range(1, 4):
    for p in product(cs, repeat=i):
        if search(''.join(p), S):
            result += 1
print(result)

ordre passé202004E

Percer en 8 minutes et demie Je pense qu'il n'y a rien de difficile parce que je l'écris exactement comme il est écrit dans l'énoncé du problème.

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

result = []
for i in range(N):
    x = i
    j = 1
    x = A[x] - 1
    while x != i:
        x = A[x] - 1
        j += 1
    result.append(j)
print(*result)

past202004 F - Digestion de la tâche

Pause en 7 minutes et demie. M'a rappelé ABC137D - Vacances d'été. Prenez simplement la tâche avec les points les plus élevés de la file d'attente de prescription et digérez-la à plusieurs reprises.

from heapq import heappush, heappop

N = int(input())

d = {}
for _ in range(N):
    A, B = map(int, input().split())
    d.setdefault(A, [])
    d[A].append(B)

t = []
result = 0
for i in range(1, N + 1):
    if i in d:
        for b in d[i]:
            heappush(t, -b)
    result += -heappop(t)
    print(result)

past202004H - 1-9 Grid

Percer en 32 minutes. Résolu avec DP qui cherche le coût minimum de tous les endroits précédents à tous les endroits suivants.

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

d = {}
for i in range(N):
    for j in range(M):
        d.setdefault(A[i][j], [])
        d[A[i][j]].append((i, j))


for i in list(range(1, 10)) + ['S', 'G']:
    if str(i) not in d:
        print(-1)
        exit()

dp = [[float('inf')] * M for _ in range(N)]
i, j = d['S'][0]
dp[i][j] = 0

current = 'S'
while current != 'G':
    if current == 'S':
        next = '1'
    elif current == '9':
        next = 'G'
    else:
        next = str(int(current) + 1)
    for i, j in d[current]:
        for ni, nj in d[next]:
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + abs(ni - i) + abs(nj - j))
    current = next


i, j = d['G'][0]
print(dp[i][j])

past202004G --String query

Percer en 23 minutes et demie. TLE est inévitable si vous créez une chaîne de caractères obéissant conformément à l'énoncé du problème, j'ai donc géré et résolu la liste des paires de caractères et de longueur.

from collections import deque

Q = int(input())

S = deque()
for _ in range(Q):
    Query = input().split()
    if Query[0] == '1':
        C = Query[1]
        X = int(Query[2])
        S.append((C, X))
    elif Query[0] == '2':
        D = int(Query[1])
        d = {}
        while D != 0 and len(S) != 0:
            C, X = S.popleft()
            d.setdefault(C, 0)
            if X >= D:
                d[C] += D
                if X != D:
                    S.appendleft((C, X - D))
                D = 0
            else:
                d[C] += X
                D -= X
        print(sum(v * v for v in d.values()))

passé202004I --Tournament

Percer en 12 minutes. Le nombre de personnes est de 2 N </ sup> et N est aussi petit que 16 ou moins, il est donc facile de le simuler docilement.

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

result = [1] * (2 ** N)
t = [(i, A[i]) for i in range(2 ** N)]
while len(t) != 1:
    nt = []
    for i in range(0, len(t), 2):
        ai, aj = t[i]
        bi, bj = t[i + 1]
        if aj > bj:
            result[ai] += 1
            nt.append(t[i])
        else:
            result[bi] += 1
            nt.append(t[i + 1])
    t = nt
result[t[0][0]] -= 1

for i in result:
    print(i)

past202004J --Analyse de la chaîne de caractères

Percer dans 20 minutes. La longueur de la chaîne de caractères finale S est inférieure ou égale à 1 000, vous pouvez donc la simuler docilement. Si vous trouvez la parenthèse gauche, recherchez la parenthèse droite appariée, et s'il y a une parenthèse à l'intérieur, continuez Puisque nous devons le traiter, écrivez le processus avec une fonction récursive et terminez.

S = input()


def f(s):
    i = s.find('(')
    if i == -1:
        return s

    result = s[:i]
    s = s[i:]
    i = 1
    n = 1
    while n != 0:
        if s[i] == '(':
            n += 1
        elif s[i] == ')':
            n -= 1
        i += 1
    t = f(s[1:i - 1])
    result += t + t[::-1]
    result += f(s[i:])
    return result


print(f(S))

past202004L - Ordre minimum du dictionnaire

Si vous l'écrivez docilement, ce sera * O * (* N * 2 </ sup>) et ce sera TLE, pensez donc à réduire la quantité de calcul. Comme il s'agit d'une méthode gourmande qui prend l'extrémité gauche de la valeur minimale de la plage sélectionnable, la valeur minimale de l'intervalle Est calculé par Segment Tree et devient * O * ( N </ i> log N </ i>).

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] * (t * 2 - 1)

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = min(self._data[i * 2 + 1], self._data[i * 2 + 2])

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

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


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

if 1 + (K - 1) * D > N:
    print(-1)
    exit()

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

result = []
i = 0
for k in range(K - 1, -1, -1):
    m = st.query(i, N - k * D)
    result.append(m)
    while A[i] != m:
        i += 1
    i += D
print(*result)

Addendum: j'ai essayé de le résoudre avec une file d'attente prioritaire comme expliqué. Je me demandais quoi faire lorsque la valeur déjà passée était laissée dans la file d'attente, alors je me demandais quoi faire quand elle devenait le minimum, mais oui, je devrais la jeter Est-ce …….

from heapq import heappush, heappop

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

if 1 + (K - 1) * D > N:
    print(-1)
    exit()

result = []
q = []
i = 0
l = 0
for k in range(K - 1, -1, -1):
    for j in range(l, N - k * D):
        heappush(q, (A[j], j))
    l = N - k * D
    while True:
        a, j = heappop(q)
        if j >= i:
            break
    result.append(a)
    i = j + D
print(*result)

Je l'ai également résolu avec Sparse Table. Dans ce problème, SegmentTree est * O * (* N * + (* N * / * D *) log N </ i>), alors que * O * ( > N </ i> log N </ i> + * N * / * D *) donc c'est un peu lent.

class SparseTable():
    _data = None
    _lookup = None
    _f = None

    def __init__(self, a):
        data = []
        lookup = []
        f = min
        b = 0
        while (1 << b) <= len(a):
            b += 1
        for _ in range(b):
            data.append([0] * (1 << b))
        data[0][:len(a)] = a
        for i in range(1, b):
            j = 0
            di = data[i]
            di1 = data[i - 1]
            while j + (1 << i) <= (1 << b):
                di[j] = f(di1[j], di1[j + (1 << (i - 1))])
                j += 1
        lookup = [0] * (len(a) + 1)
        for i in range(2, len(lookup)):
            lookup[i] = lookup[i >> 1] + 1
        self._data = data
        self._lookup = lookup
        self._f = f

    def query(self, start, stop):
        b = self._lookup[stop - start]
        db = self._data[b]
        return self._f(db[start], db[stop - (1 << b)])


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

if 1 + (K - 1) * D > N:
    print(-1)
    exit()

st = SparseTable(A)

result = []
i = 0
for k in range(K - 1, -1, -1):
    m = st.query(i, N - k * D)
    result.append(m)
    while A[i] != m:
        i += 1
    i += D
print(*result)

past202004K --brackets

Je ne peux pas percer. Je fais TLE, mais je ne peux même pas écrire une implémentation naïve qui donne la bonne réponse.

Recommended Posts