AtCoder Grand Contest Past Question Challenge 2

AtCoder Grand Contest Past Question Challenge 2

AGC009A - Multiple Array

Il est facile de voir que le bouton A N </ sub> est enfoncé dans l'ordre inverse du bouton A 1 </ sub>. A i </ sub> est B i < Un multiple de / sub> signifie A i </ sub> mod B i </ sub> = 0, donc A i </ sub> mod B Lorsque i </ sub> n'est pas 0, appuyez sur B i </ sub> --A i </ sub> mod B i </ sub> fois. Au fait, d'ici là Notez que A i </ sub> augmente du nombre de fois que vous appuyez dessus. Sur la base de ce qui précède, j'ai écrit le code suivant pour demander une réponse.

N = int(input())

A = [None] * N
B = [None] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

result = 0
for i in range(N - 1, -1, -1):
    t = (A[i] + result) % B[i]
    if t != 0:
        result += B[i] - t
print(result)

AGC011A - Airport Bus

Le bus part lorsque la limite de temps de la première personne qui attend arrive maintenant ou que la personne qui attend devient des personnes C. Donc, mettez la limite de temps de la première personne et le nombre actuel de personnes en attente dans les variables. Il suffit de tourner la boucle. Notez que le temps T i </ sub> n'augmente pas de façon monotone, même s'il s'agit du i-ème passager.

N, C, K = map(int, input().split())
T = [int(input()) for _ in range(N)]
T.sort()

c = 0
l = float('inf')
result = 0
for i in range(N):
    t = T[i]
    if t > l:
        result += 1
        l = float('inf')
        c = 0
    if c == 0:
        l = t + K
    c += 1
    if c == C:
        result += 1
        l = float('inf')
        c = 0
if c != 0:
    result += 1
print(result)

AGC034A - Kenken Race

C'est facile pour les humains à faire à la main, mais je gémissais que c'était ennuyeux à mettre en œuvre, mais j'ai juste oublié que je ne pouvais aller que vers la droite (rires). La priorité est donnée à celui avec le but à droite. Si vous ne pouvez pas le déplacer, déplacez l'autre, et si vous ne pouvez pas déplacer les deux, affichez Non, c'est tout.

N, A, B, C, D = map(int, input().split())
S = input()


def move_snuke():
    global A, B
    if B == D:
        return False
    if S[B + 1] == '.' and A != B + 1:
        B += 1
        return True
    if S[B + 2] == '.' and A != B + 2:
        B += 2
        return True
    return False


def move_fnuke():
    global A, B
    if A == C:
        return False
    if S[A + 1] == '.' and B != A + 1:
        A += 1
        return True
    if S[A + 2] == '.' and B != A + 2:
        A += 2
        return True
    return False


S = '#' + S
while True:
    if C < D:
        if not move_snuke():
            if not move_fnuke():
                print('No')
                break
    else:
        if not move_fnuke():
            if not move_snuke():
                print('No')
                break
    if A == C and B == D:
        print('Yes')
        break

AGC035A - XOR Circle

Si le premier est a et le second est b, le troisième est un xor b, le quatrième est a, le cinquième est b et seuls trois types de nombres apparaissent. Donc, a i < S'il y a 4 types ou plus de nombres / sub>, vous pouvez définir Non à ce stade. S'il y a 3 types, il n'y a que 9 types dans les 2 premiers et même si vous simulez toutes les combinaisons, N ≤ 10 5 </ sup > De au maximum O (9 × 10 5 </ sup>), AC est possible.

from itertools import product

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

c = {}
for e in a:
    c.setdefault(e, 0)
    c[e] += 1

if len(set(c)) > 3:
    print('No')
    exit()

t = {}
for x, y in product(set(c), repeat=2):
    i = x
    j = y
    t[i] = 1
    if t[i] > c[i]:
        continue
    t.setdefault(j, 0)
    t[j] += 1
    if t[j] > c[j]:
        continue
    for _ in range(N - 2):
        k = i ^ j
        t.setdefault(k, 0)
        t[k] += 1
        c.setdefault(k, 0)
        if t[k] > c[k]:
            j = -1
            break
        i, j = j, k
    if j ^ x == y:
        print('Yes')
        exit()
print('No')

AGC028A - Two Abbreviations

Puisque L est divisible par N et M, il est un multiple du multiple commun minimum de N et M. Lorsque L / N * i == L / M * j, il doit être S [i] == T [j], Même si L devient L * a, la paire de i et j à comparer ne change pas car elle n'est multipliée par a que des deux côtés. Puisque la réponse est la plus courte, L est le multiple commun minimum de N et M. Devenir.

from fractions import gcd


def lcm(x, y):
    return x // gcd(x, y) * y


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

for i in range(N):
    if M * i % N == 0 and S[i] != T[M * i // N]:
        print(-1)
        exit()
print(lcm(N, M))

AGC022A - Diverse Word

Le prochain mot coloré est

  1. Si la longueur de la chaîne est inférieure à 26, ajoutez les plus petits caractères inutilisés dans l'ordre lexical.
  2. Si la longueur de la chaîne de caractères est de 26 caractères, prenez le dernier caractère et ajoutez le dernier caractère qui est plus grand que le dernier caractère et le plus petit dans l'ordre du dictionnaire. S'il n'y a rien de tel, prenez la dernière lettre et répétez.

Sera.

Après tout, il s'agit d'une chaîne de caractères d'une longueur maximale de 26, donc il n'y a aucun problème à l'ajouter ou à l'ajouter, donc la mise en œuvre n'est pas si difficile.

def next_diverse_word(s):
    alphabets = set(chr(ord('a') + i) for i in range(26))
    if s == 'zyxwvutsrqponmlkjihgfedcba':
        return -1
    r = alphabets - set(s)
    if len(r) != 0:
        return s + sorted(r)[0]
    s = list(s)
    r = [s[-1]]
    s = s[:-1]
    while True:
        k = s[-1]
        r.append(s[-1])
        s = s[:-1]
        t = [c for c in r if c > k]
        if len(t) != 0:
            s.append(sorted(t)[0])
            return ''.join(s)


S = input()
print(next_diverse_word(S))

Recommended Posts

AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Défi des questions passées 1
Concours AtCoder pour débutants Défi des questions passées 6
Concours AtCoder pour débutants Défi des questions passées 4
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
Examen des questions passées d'AtCoder (12/5)
AtCoder Grand Contest 048 Critique
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
AtCoder Grand Contest 046 Critique
AtCoder Grand Contest 041 Rapport de participation
AtCoder Grand Contest 040 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
Défiez AtCoder
AtCoder Beginner Contest 066 Revoir les questions précédentes
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 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 127 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 067 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 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 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 126 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 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes