Rapport de participation au test pratique du 3e algorithme AtCoder

Rapport de participation au test pratique du 3e algorithme AtCoder

C'est gratuit, et chokudai a dit que je voulais que vous le receviez, alors j'ai participé à la vraie chose contrairement aux deux dernières fois. Le résultat est intermédiaire avec 70 points. La première fois est de 64 points, la deuxième fois est de 76 points Parce que c'est un point, c'est juste au milieu. Je le faisais tôt le matin comme les deux dernières fois, mais comme j'ai dormi pendant 3 heures, je ne pouvais pas m'empêcher d'être somnolent du milieu. C'est peut-être la raison pour laquelle il y avait beaucoup de WA. Je pense au reste, mais je pense que ça va parce que même une tête rafraîchissante peut être résolue et il ne reste qu'une question.

past202005A - Case Sensitive

Percer en 2 minutes. Il suffit d'écrire.

s = input()
t = input()

if s == t:
    print('same')
elif s.lower() == t.lower():
    print('case-insensitive')
else:
    print('different')

past202005B - Scoring dynamique

Cela se fait en 10 minutes et demie. C'est assez difficile même si c'est un problème B!? Au début, cela prend beaucoup de temps parce que la personne qui a résolu la formule de yukicoder tôt a mal compris que c'était le type avec un score élevé.

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

score = [N] * (M + 1)
answered = [[False] * (M + 1) for _ in range(N + 1)]
for _ in range(Q):
    s = list(map(int, input().split()))
    if s[0] == 1:
        t = 0
        for i in range(1, M + 1):
            if answered[s[1]][i]:
                t += score[i]
        print(t)
    elif s[0] == 2:
        score[s[2]] -= 1
        answered[s[1]][s[2]] = True

séquence de ratio past202005C-égal

Rompre en 13 minutes et demie. Problème TLE2, WA1. C, mais écriture de TLE naïf! En faisant un bug et en mangeant WA, AC.

Explication Implémentation de référence PDF, setrecursionlimit n'a pas de sens, et je ne suis pas sûr que sys.stdin.buffer.readline soit utilisé à la place de sys.stdin.readline, ʻa * r ** (n -1) `Est un maximum de 10 9 + 9 29 </ sup> </ sup>, mais je me demande si c'est bon. O (log N </ i>) Je me demande si je veux éviter d'écrire.

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

result = A
a = R
b = N - 1
while b != 0 and result <= 1000000000:
    if b & 1 != 0:
        result *= a
    a *= a
    b >>= 1

if result > 1000000000:
    print('large')
else:
    print(result)

past202005D - Tableau d'affichage électrique

Il a éclaté en 9 minutes et demie, ce n'était pas trop difficile parce que j'ai simplement coupé chaque personnage et l'ai mis en correspondance.

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

a = [
    '.###..#..###.###.#.#.###.###.###.###.###.',
    '.#.#.##....#...#.#.#.#...#.....#.#.#.#.#.',
    '.#.#..#..###.###.###.###.###...#.###.###.',
    '.#.#..#..#.....#...#...#.#.#...#.#.#...#.',
    '.###.###.###.###...#.###.###...#.###.###.'
]

result = []
for i in range(N):
    t = [s[j][i * 4:(i + 1) * 4] for j in range(5)]
    for j in range(10):
        for k in range(5):
            if t[k] != a[k][j * 4:(j + 1) * 4]:
                break
        else:
            result.append(j)
            break
print(''.join(str(i) for i in result))

past202005E --Sprinkler

Percer dans 8 minutes et demie. Même si je lis l'énoncé du problème, je ne sais pas si la couleur de l'arroseur en cours d'exécution va changer, mais je pense que je devrais la changer quand elle deviendra WA, et la soumettre après AC. De ce point de vue, ce serait un problème si les sprinkleurs en cours d'exécution étaient adjacents les uns aux autres, donc il démarrerait et s'arrêterait réellement, puis la requête suivante.

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

links = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v = map(int, input().split())
    links[u].append(v)
    links[v].append(u)
c = [0] + list(map(int, input().split()))

for _ in range(Q):
    s = list(map(int, input().split()))
    if s[0] == 1:
        x = s[1]
        print(c[x])
        for y in links[x]:
            c[y] = c[x]
    if s[0] == 2:
        x, y = s[1:]
        print(c[x])
        c[x] = y

past202005G --Grid Gold Move

Il a percé en 40 minutes et demie WA2 J'ai oublié de sortir -1 quand il était inaccessible et de sortir l'infini. J'ai perdu mon temps parce que je n'ai pas pu obtenir l'exemple d'entrée. Eh bien, ce n'est pas si difficile car c'est une recherche avec priorité à la largeur qui me fait penser au nombre de fois que je l'écrirai. −200 ≤ x i </ sub>, y i </ sub>, X, Y ≤ 200 Cependant, si vous en faites un espace, il sera impossible de passer à côté de l'obstacle à la fin, mais ce sera infranchissable. Notez que vous devez étaler un par un en haut, en bas, à gauche et à droite.

from collections import deque

INF = float('inf')

N, X, Y = map(int, input().split())

t = [['.'] * 403 for _ in range(403)]
for _ in range(N):
    x, y = map(int, input().split())
    t[y + 201][x + 201] = '#'

d = [[INF] * 403 for _ in range(403)]
d[0 + 201][0 + 201] = 0
q = deque([(0, 0)])
while q:
    y, x = q.popleft()
    i, j = y + 201, x + 201
    if i + 1 < 403 and j - 1 >= 0 and t[i + 1][j - 1] != '#' and d[i + 1][j - 1] > d[i][j] + 1:
        d[i + 1][j - 1] = d[i][j] + 1
        q.append((y + 1, x - 1))
    if i + 1 < 403 and j + 1 < 403 and t[i + 1][j + 1] != '#' and d[i + 1][j + 1] > d[i][j] + 1:
        d[i + 1][j + 1] = d[i][j] + 1
        q.append((y + 1, x + 1))
    if i - 1 >= 0 and t[i - 1][j] != '#' and d[i - 1][j] > d[i][j] + 1:
        d[i - 1][j] = d[i][j] + 1
        q.append((y - 1, x))
    if i + 1 < 403 and t[i + 1][j] != '#' and d[i + 1][j] > d[i][j] + 1:
        d[i + 1][j] = d[i][j] + 1
        q.append((y + 1, x))
    if j - 1 >= 0 and t[i][j - 1] != '#' and d[i][j - 1] > d[i][j] + 1:
        d[i][j - 1] = d[i][j] + 1
        q.append((y, x - 1))
    if j + 1 < 403 and t[i][j + 1] != '#' and d[i][j + 1] > d[i][j] + 1:
        d[i][j + 1] = d[i][j] + 1
        q.append((y, x + 1))
if d[Y + 201][X + 201] == INF:
    print(-1)
else:
    print(d[Y + 201][X + 201])

past202005F - Matrice de circulation

Percer en 40 minutes et demie. WA4. Une catastrophe car il s'agit de prendre des caractères de chaque ligne de la matrice et de faire une circulaire, mais mal comprendre que c'est un problème de faire une circulaire en utilisant tous les caractères de la matrice. Je pense que vous pouvez le résoudre si vous savez.

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

t = ''
for i in range(N // 2):
    u = list(set(a[i]) & set(a[N - 1 - i]))
    if len(u) == 0:
        print(-1)
        exit()
    t += u[0]

if N % 2 == 0:
    print(t + t[::-1])
else:
    print(t + a[N // 2][0] + t[::-1])

past202005J - Sushi rotatif

Il éclate en 27 minutes et demie Je me suis souvenu de ABC134E --Sequence Decomposing.

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

eater = [-1] * M
eater[0] = 1
t = [-1] * N
t[0] = a[0]
for i in range(1, M):
    ng = -1
    ok = N
    while abs(ng - ok) > 1:
        m = (ok + ng) // 2
        if a[i] > t[m]:
            ok = m
        else:
            ng = m
    if ok != N:
        t[ok] = a[i]
        eater[i] = ok + 1
print('\n'.join(str(i) for i in eater))

past202005I --Matrix operation

Percer en 68 minutes WA2, TLE2, RE2. N ≤ 10 5 </ sup> Faire une liste de N × N sans la voir. Génération stupide. Puisqu'il s'agit d'un désastre, je le traite avec O (1) dans la table de lecture, mais j'ai perdu du temps à oublier que l'échange de lignes et de colonnes est permuté au moment de la translocation. N'y a-t-il pas beaucoup de problèmes de requête cette fois? (3 questions) Œil).

from sys import stdin
readline = stdin.readline

N = int(readline())
Q = int(readline())

result = []
transposed = False
rows = list(range(N + 1))
cols = list(range(N + 1))
for _ in range(Q):
    Query = list(map(int, readline().split()))
    if Query[0] == 1:
        A, B = Query[1:]
        if not transposed:
            t = rows[A]
            rows[A] = rows[B]
            rows[B] = t
        else:
            t = cols[A]
            cols[A] = cols[B]
            cols[B] = t
    elif Query[0] == 2:
        A, B = Query[1:]
        if not transposed:
            t = cols[A]
            cols[A] = cols[B]
            cols[B] = t
        else:
            t = rows[A]
            rows[A] = rows[B]
            rows[B] = t
    elif Query[0] == 3:
        transposed = not transposed
    elif Query[0] == 4:
        A, B = Query[1:]
        y, x = A, B
        if transposed:
            y, x = x, y
        y = rows[y]
        x = cols[x]
        result.append(N * (y - 1) + x - 1)
print('\n'.join(str(i) for i in result))

past202005H --Hall run

Percer en 63 minutes et demie. WA2, RE1. Le plus gros problème cette fois. Si vous pensez que c'est un simple problème avec un DP de distribuer WA. Je ne comprends pas vraiment pourquoi, je suppose que j'ai fait une erreur, alors je l'ai réécrit en langage Go Au moment où j'ai écrit T1 / 2 au milieu de l'écriture, j'ai pensé que je l'éviterais et j'ai dit:" Pourquoi écrivez-vous T1 * 0.5. C'est un nombre à virgule flottante !!!" Remarqué AC.

N, L = map(int, input().split())
x = set(map(int, input().split()))
T1, T2, T3 = map(int, input().split())

dp = [float('inf')] * (L + 4)
dp[0] = 0
for i in range(L):
    a = dp[i] + T1
    if i + 1 in x:
        a += T3
    if dp[i + 1] > a:
        dp[i + 1] = a

    a = dp[i] + T1 + T2
    if i + 2 in x:
        a += T3
    if dp[i + 2] > a:
        dp[i + 2] = a

    a = dp[i] + T1 + T2 * 3
    if i + 4 in x:
        a += T3
    if dp[i + 4] > a:
        dp[i + 4] = a

result = dp[L]
result = min(result, dp[L - 1] + T1 // 2 + T2 // 2)
result = min(result, dp[L - 2] + T1 // 2 + 3 * T2 // 2)
result = min(result, dp[L - 3] + T1 // 2 + 5 * T2 // 2)
print(result)

past202005K --Move container

J'ai abandonné car il me restait 20 minutes. Quoi qu'il en soit, je dois résoudre 2 questions pour devenir une personne avancée. Si je n'enregistre que ce qui est en dessous, je peux me déplacer avec O (1), mais quel bureau est allumé maintenant? Is O (* N *), je me demandais quoi faire, mais cette fois il y a beaucoup de problèmes de requêtes (4ème question).

passé202005L --Supermarket

J'ai abandonné car il me restait 20 minutes. Quoi qu'il en soit, je dois résoudre 2 questions avant de pouvoir devenir un joueur avancé 1 ≤ a i </ sub> ≤ 2 Alors puis-je avoir deux files d'attente prioritaires? Is O (* N *), alors j'ai pensé que ce serait impossible, peut-être un arbre de dichotomie équilibré.

Recommended Posts

Rapport de participation au test pratique du 3e algorithme AtCoder
AtCoder 1st Algorithm Practical Test Virtual Participation Report
AtCoder 2nd Algorithm Practical Test Virtual Participation Report
Explication du 3e test pratique de l'algorithme (PAST) (Python)
AtCoder Judge System Update Test Contest 202004 Rapport de participation
AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 151 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Beginner Contest 154 Rapport de participation
AtCoder Grand Contest 041 Rapport de participation
AtCoder Beginner Contest 166 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 164 Rapport de participation
Rapport de participation au concours régulier AtCoder 105
Rapport de participation au concours AtCoder Débutant 150
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 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
rapport de participation abc154
rapport de participation abc155
AtCoder Sumitomo Mitsui Trust Bank Programming Contest 2019 Rapport de participation
1er test pratique d'algorithme Résoudre les questions passées avec python
Rapport de participation PyCon JP 2017
AtCoder Hitachi, Ltd.Rapport de participation au concours de programmation de la Division des systèmes sociaux 2020
2e test pratique de l'algorithme Résoudre les questions précédentes avec python (inachevé)