AtCoder 1st Algorithm Practical Test Virtual Participation Report

AtCoder 1st Algorithm Practical Test Virtual Participation Report

J'ai finalement eu un peu de temps, alors j'ai essayé la participation virtuelle à PAST. Le résultat était de 64 points, donc c'était intermédiaire (60-79 points). Contrairement au jeu mathématique et inspirant habituel d'AtCoder, l'implémentation est quelque chose Il y avait beaucoup de problèmes qui semblaient subtilement gênants, et je sentais que la couleur des cheveux était un peu différente.

passé201912A-Double vérification

Rompre dans 3 minutes et demie. Vérifiez s'il ne s'agit que d'un nombre et, s'il est correct, convertissez-le en int et affichez-le au double.

S = input()

for i in range(3):
    if S[i] not in '0123456789':
        print('error')
        exit()
print(int(S) * 2)

passé201912B - Gestion des augmentations / diminutions

Percer en 7 minutes. Il suffit de comparer avec la valeur et la sortie précédentes.

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

prev = A[0]
for i in range(1, N):
    if A[i] == prev:
        print('stay')
    elif A[i] < prev:
        print('down %d' % (prev - A[i]))
    elif A[i] > prev:
        print('up %d' % (A[i] - prev))
    prev = A[i]

passé201912C - Troisième

Passez en 2 minutes. Triez simplement par ordre décroissant et sortez la troisième valeur par l'avant.

ABCDEF = list(map(int, input().split()))

ABCDEF.sort(reverse=True)
print(ABCDEF[2])

past201912D - Inspection en double

Faites une percée en 11 minutes. Il vous suffit de compter le nombre d'apparitions dans le dictionnaire, d'identifier 0 et 2 choses, et de sortir.

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

t = set(A)
if len(t) == N:
    print('Correct')
    exit()

d = {}
for i in range(N):
    if A[i] in d:
        d[A[i]] += 1
    else:
        d[A[i]] = 1

for i in range(1, N + 1):
    if i not in d:
        x = i
    elif d[i] == 2:
        y = i

print(y, x)

passé201912E - Journal SNS

Percée en 24 minutes. La mise en œuvre du suivi de suivi a également ajouté les utilisateurs qui suivent le suivi qui ont augmenté au cours du traitement, et il a fallu du temps pour que l'exemple d'entrée 1 ne réussisse pas. L'exemple d'entrée 1 l'a détecté. Je pense que cela aurait pris plus de temps si vous ne l'aviez pas fait.

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

t = [['N'] * N for _ in range(N)]
for _ in range(Q):
    S = input()
    if S[0] == '1':
        _, a, b = map(int, S.split())
        t[a - 1][b - 1] = 'Y'
    elif S[0] == '2':
        _, a = map(int, S.split())
        for i in range(N):
            if t[i][a - 1] == 'Y':
                t[a - 1][i] = 'Y'
    elif S[0] == '3':
        _, a = map(int, S.split())
        for i in [i for i in range(N) if t[a - 1][i] == 'Y']:
            for j in range(N):
                if t[i][j] == 'Y' and j != a - 1:
                    t[a - 1][j] = 'Y'

for i in range(N):
    print(''.join(t[i]))

past201912F - DoubleCamelCase Sort

Il n'y a rien de particulièrement difficile, il suffit de découper les mots, de les trier par casse et de les combiner.

S = input()

t = []
start = -1
for i in range(len(S)):
    if S[i].isupper():
        if start == -1:
            start = i
        else:
            t.append(S[start:i+1])
            start = -1
t.sort(key=str.lower)
print(''.join(t))

passé201912G --Groupage

Il a éclaté en 20 minutes, je pensais que je ne savais pas au début, mais quand j'ai regardé de près, je pouvais faire un round robin parce que N≤10. Ce n'était pas particulièrement difficile.

N = int(input())
a = [list(map(int, input().split())) for _ in range(N - 1)]

result = -float('inf')
t = [0] * N
for _ in range(3 ** N):
    s = 0
    for i in range(N):
        for j in range(i + 1, N):
            if t[i] == t[j]:
                s += a[i][j - i - 1]
    result = max(result, s)
    for i in range(N):
        if t[i] < 2:
            t[i] += 1
            break
        t[i] = 0
print(result)

passé201912H - Vente en gros

Il se produit en 44 minutes et demie. Il est inévitable que TLE reflète à la fois les ventes d'ensemble et tous les types de ventes dans le tableau en raison des restrictions. J'ai donc créé une variable cumulative pour chacune d'elles et l'ai transmise avec une politique de correspondance avec Tsuji. Il m'a fallu beaucoup de temps pour remarquer que ʻodd_min- = a` avait été divulgué.

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

all_min = min(C)
odd_min = min(C[::2])
all_sale = 0
odd_sale = 0
ind_sale = 0
for _ in range(Q):
    S = input()
    if S[0] == '1':
        _, x, a = map(int, S.split())
        t = C[x - 1] - all_sale - a
        if x % 2 == 1:
            t -= odd_sale
        if t >= 0:
            ind_sale += a
            C[x - 1] -= a
            all_min = min(all_min, t)
            if x % 2 == 1:
                odd_min = min(odd_min, t)
    elif S[0] == '2':
        _, a = map(int, S.split())
        if odd_min >= a:
            odd_sale += a
            odd_min -= a
            all_min = min(odd_min, all_min)
    elif S[0] == '3':
        _, a = map(int, S.split())
        if all_min >= a:
            all_sale += a
            all_min -= a
            odd_min -= a
print(all_sale * N + odd_sale * ((N + 1) // 2) + ind_sale)

passé201912I - Achats de pièces

Il passe en 14 minutes. C'est DP, donc ce n'est pas particulièrement difficile. Il suffit de convertir Y en 1 et N en 0, qui est considéré comme un peu de chaque chiffre, puis DP.

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


def conv(S):
    result = 0
    for c in S:
        result *= 2
        if c == 'Y':
            result += 1
    return result


dp = [-1] * 2001
dp[0] = 0
for _ in range(M):
    S, C = input().split()
    S = conv(S)
    C = int(C)
    for i in range(2000, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i | S] == -1 or dp[i | S] > dp[i] + C:
            dp[i | S] = dp[i] + C
print(dp[(1 << N) - 1])

past201912J - nivellement du sol

Je n'ai pas pu percer. Trouvez l'itinéraire le moins cher du coin inférieur gauche vers le coin inférieur droit avec DP, réécrivez l'endroit où je suis retourné en arrière jusqu'à 0, trouvez l'itinéraire le moins cher du coin inférieur droit vers le coin supérieur droit avec DP, et le coût de chacun J'ai essayé de faire une implémentation qui résume, mais environ la moitié WA.

Post-scriptum: résolu selon l'explication.

from heapq import heappop, heappush

INF = float('inf')


def cost_from(H, W, A, y0, x0):
    dp = [[INF] * W for _ in range(H)]
    dp[y0][x0] = 0
    q = [(0, y0, x0)]
    while q:
        c, y, x = heappop(q)
        t = dp[y][x]
        if t != c:
            continue
        if y - 1 >= 0:
            u = t + A[y - 1][x]
            if dp[y - 1][x] > u:
                dp[y - 1][x] = u
                heappush(q, (u, y - 1, x))
        if y + 1 < H:
            u = t + A[y + 1][x]
            if dp[y + 1][x] > u:
                dp[y + 1][x] = t + A[y + 1][x]
                heappush(q, (u, y + 1, x))
        if x - 1 >= 0:
            u = t + A[y][x - 1]
            if dp[y][x - 1] > u:
                dp[y][x - 1] = u
                heappush(q, (u, y, x - 1))
        if x + 1 < W:
            u = t + A[y][x + 1]
            if dp[y][x + 1] > u:
                dp[y][x + 1] = u
                heappush(q, (u, y, x + 1))
    return dp


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

result = INF
cost1 = cost_from(H, W, A, H - 1, 0)
cost2 = cost_from(H, W, A, H - 1, W - 1)
cost3 = cost_from(H, W, A, 0, W - 1)
for i in range(H):
    for j in range(W):
        t = cost1[i][j] + cost2[i][j] + cost3[i][j] - 2 * A[i][j]
        if t < result:
            result = t
print(result)

passé201912K - Entreprise géante

Je ne pouvais pas percer, bien sûr, je pourrais écrire une implémentation naïve, mais je ne pouvais penser à aucun moyen de réduire la quantité de calcul.

Post-scriptum: J'ai appris la tournée des pétroliers et la climatisation.

N = int(input())

root = -1
children = [[] for _ in range(N + 1)]
left = [0] * (N + 1)
right = [0] * (N + 1)

for i in range(1, N + 1):
    p = int(input())
    if p == -1:
        root = i
    else:
        children[p].append(i)

i = 0
s = [root]
while s:
    n = s.pop()
    if n > 0:
        left[n] = i
        i += 1
        s.append(-n)
        for c in children[n]:
            s.append(c)
    else:
        right[-n] = i

Q = int(input())
result = []
for _ in range(Q):
    a, b = map(int, input().split())
    if left[b] < left[a] < right[b]:
        result.append('Yes')
    else:
        result.append('No')
print('\n'.join(result))

J'ai aussi essayé de le résoudre en doublant.

from math import log
from collections import deque
from sys import stdin

readline = stdin.readline

N = int(readline())

root = -1
children = [[] for _ in range(N + 1)]
parent = [[-1] * (N + 1) for _ in range(18)]

for i in range(1, N + 1):
    p = int(readline())
    parent[0][i] = p
    if p == -1:
        root = i
    else:
        children[p].append(i)

for i in range(1, 18):
    parenti1 = parent[i - 1]
    parenti = parent[i]
    for j in range(1, N + 1):
        t = parenti1[j]
        if t == -1:
            parenti[j] = -1
        else:
            parenti[j] = parenti1[t]

depth = [-1] * (N + 1)
q = deque([(root, 0)])
while q:
    n, d = q.pop()
    depth[n] = d
    for c in children[n]:
        q.append((c, d + 1))

Q = int(input())
result = []
for _ in range(Q):
    a, b = map(int, readline().split())
    if depth[a] <= depth[b]:
        result.append('No')
        continue
    while depth[a] != depth[b]:
        t = int(log(depth[a] - depth[b], 2))
        a = parent[t][a]
    if a == b:
        result.append('Yes')
    else:
        result.append('No')
print('\n'.join(result))

Recommended Posts

AtCoder 1st Algorithm Practical Test Virtual Participation Report
AtCoder 2nd Algorithm Practical Test Virtual Participation Report
Rapport de participation au test pratique du 3e algorithme AtCoder
AtCoder Judge System Update Test Contest 202004 Rapport de participation
1er test pratique d'algorithme Résoudre les questions passées avec python
AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 161 Rapport de participation
AtCoder Beginner Contest 151 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Grand Contest 041 Rapport de participation
AtCoder Grand Contest 040 Rapport de participation
AtCoder Beginner Contest 153 Rapport de participation
AtCoder Beginner Contest 145 Rapport de participation
AtCoder Débutant Contest 184 Rapport de participation
AtCoder Beginner Contest 165 Rapport de participation
Rapport de participation au concours AtCoder Débutant 160
AtCoder Beginner Contest 169 Rapport de participation
AtCoder Beginner Contest 178 Rapport de participation
AtCoder Beginner Contest 163 Rapport de participation
AtCoder Beginner Contest 159 Rapport de participation
AtCoder Beginner Contest 164 Rapport de participation
Rapport de participation au concours régulier AtCoder 105
AtCoder Beginner Contest 168 Rapport de participation
Rapport de participation au concours AtCoder Débutant 150
AtCoder Beginner Contest 158 Rapport de participation
Rapport de participation au concours AtCoder Débutant 180
AtCoder Regular Contest 104 Rapport de participation
AtCoder Beginner Contest 156 Rapport de participation
AtCoder Beginner Contest 162 Rapport de participation
AtCoder Débutant Contest 157 Rapport de participation
AtCoder Beginner Contest 167 Rapport de participation
AtCoder Débutant Contest 179 Rapport de participation
Concours AtCoder Débutant 182
AtCoder Beginner Contest 146 Rapport de participation
AtCoder Beginner Contest 152 Rapport de participation
AtCoder Débutant Contest 155 Rapport de participation
AtCoder Beginner Contest 174 Rapport de participation
AtCoder Beginner Contest 171 Rapport de participation
AtCoder Beginner Contest 149 Rapport de participation
AtCoder Beginner Contest 148 Rapport de participation
AtCoder Débutant Contest 170 Rapport de participation
AtCoder Chokudai Contest 005 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
AtCoder Débutant Contest 183 Rapport de participation
Rapport de participation au concours de programmation AtCoder HHKB 2020
Rapport de participation au concours de programmation AtCoder Acing 2020
Rapport de participation au concours de programmation AtCoder Keyence 2020
Rapport de participation au concours de programmation AtCoder Panasonic 2020
Rapport de participation au concours d'entraînement de la bibliothèque AtCoder (Python)
AtCoder Introduction au rapport de participation au concours Heuristique
Explication du 3e test pratique de l'algorithme (PAST) (Python)
rapport de participation abc154
rapport de participation abc155
AtCoder Sumitomo Mitsui Trust Bank Programming Contest 2019 Rapport de participation