Examen de atcoder ABC158, jusqu'à la question E (Python)

3/14 Corrigé en fonction du commentaire. Merci beaucoup.

Compétitif Pro Un débutant complet a commencé à participer à Atcoder, je vais donc écrire un article pour étudier. Cliquez ici pour les concours auxquels vous avez participé. [AtCoder Beginner Contest 158] (https://atcoder.jp/contests/abc158)

Le langage sera Python. Le but est un examen, donc ce n'est pas la solution que j'ai trouvée. J'écris en regardant les explications et autres réponses. A - Station and Bus Une chaîne de caractères est-elle donnée comme information sur la station et comprend-elle deux types de stations, la société A et la société B? C'est le problème.

Dans la soumission réelle, j'ai honnêtement tourné la chaîne pour voir si elle contenait une station différente. Dans ce cas, seules trois chaînes de caractères sont données, vous pouvez donc simplement les comparer.

s = input()
if s[0] == s[1] or s[1] == s[2]: print('No')
else: print('Yes')

B - Count Balls Si vous mettez un nombre fixe de boules bleues et rouges, combien de bleus sont inclus par un point spécifique? C'est le problème.

Honnêtement, quand j'ai essayé de le tourner avec for, le temps de calcul était terminé. Je réalise enfin que ce n'est pas un tel jeu. Je l'ai soumis avec un code beaucoup plus sale que ci-dessous.

N, A, B = map(int, input().split())
out = N // (A + B) * A
rem = min(N % (A + B), A)
print(out + rem)

J'ai pensé après avoir vu l'explication que le calcul du reste est pratique pour trouver le nombre restant.

C - Tax Increase Existe-t-il un prix unitaire de A yen avec le taux d'imposition réduit appliqué et de B yen sans celui-ci? C'est le problème.

Afin de réduire la plage de calcul, définissez d'abord les valeurs minimum et maximum qui satisfont la condition de A, puis vérifiez si la condition de B est satisfaite dans cette plage. Spécifier cette plage était gênant, et bien que j'étais au niveau arithmétique, j'étais confus et foiré.

import math
A, B = map(int, input().split())
minV = math.ceil(A / 0.08)
maxV = (A + 1) // 0.08
for i in range(minV, maxV):
    if int(i * 0.1) == B:
        print(i)
        exit()
print(-1)

Cependant, dans ce problème, le réglage d'une plage étroite de $ 1 \ leq A, B \ leq 100 $ est clairement indiqué dès le début, il semble donc qu'il était bon de rechercher docilement à partir de 1. Puisque la quantité de calcul est O (n), c'est bien mieux que de se boucher avec des choses supplémentaires.

A, B = map(int, input().split())
maxV = 1010 #Toute valeur supérieure à cela ne satisfera jamais à la condition B.
for i in range(1, maxV):
    if int(i * 0.08) == A and int(i * 0.1) == B:
        print(i)
        exit()
print(-1)

D - String Formation C'est un problème de changer la chaîne de caractères selon la commande donnée.

J'ai écrit ce qui suit d'une manière simple. J'ai soumis une telle réponse et le temps de calcul était terminé.

s = input()
n = int(input())
for i in range(n):
    Q = input().split()
    if Q[0] == '1':
        s = s[::-1]
    else:
        if Q[1] == '1':
            s = Q[2] + s
        else:
            s = s + Q[2]
print(s)

Selon l'explication, il semble qu'il faut du temps à chaque opération pour inverser la chaîne de caractères. Au lieu de le retourner, vous devriez garder des informations sur le fait qu'il soit ou non. De plus, comme l'ajout au début du tableau prend du temps, il semble nécessaire d'ajouter à la fin du tableau.

C'est pourquoi j'ai ajouté une variable isReverse qui indique "si elle est inversée". Ajout de la variable top qui stocke les informations au début afin que ce soit toujours le "processus à ajouter à la fin" de la chaîne de caractères.

s = input()
top = ''
n = int(input())
isReverse = False
for i in range(n):
    Q = input().split()
    if(Q[0] == '1'):
        isReverse = not isReverse
    else:
        if Q[1] == '1':
            if isReverse: s += Q[2]
            else: top += Q[2]
        else:
            if isReverse: top += Q[2]
            else: s += Q[2]
if isReverse: s = s[::-1] + top
else: s = top[::-1] + s
print(s)

Vous pouvez maintenant le faire à temps.

E - Divisible Substring

La question est de savoir combien d'intervalles sont divisibles par $ p $ dans une séquence donnée de nombres.

C'est ce que j'ai soumis. J'ai vérifié toutes les séquences et calculé $ O (n ^ 2) $, et bien sûr, le temps était écoulé.

n, p = map(int,input().split())
s = input()
count = 0
for i in range(n):
    for j in range(1, n - i + 1):
        num = int(s[i: i + j])
        if num % p == 0:
            count += 1
print(count)

Cela semble exiger des techniques mathématiques. J'ai regardé la vidéo du commentaire car il était difficile de lire le commentaire.

Commencez par numéroter la chaîne de caractères donnée à partir de la droite.

D = [d_N, d_{N - 1}, \cdots, d_1, d_0]

La valeur obtenue en multipliant chaque valeur par 10 $ ^ i $ est la valeur que vous voulez réellement gérer.

D' = [d_N\times 10^N, d_{N - 1}\times 10^{N- 1}, \cdots, d_1\times 10, d_0]

Considérez le reste de la division de $ p $ pour chaque nombre de chiffres. Cependant, «lors de la division par 2» et «lors de la division par 5» sont exclus car ils interfèrent avec le multiplicateur de 10. Par conséquent, nous classerons les cas. (i) Pour $ p \ neq 2, 5 $

M = [(d_N\times 10^N)\% p, (d_{N - 1}\times 10^{N- 1})\% p, \cdots, (d_1\times 10)\% p, (d_0)\% p]

Exprimons le terme de reste obtenu comme $ m_i . $ M = [m_N, m_{N - 1}, \cdots, m_1, m_0]$$ La somme des nombres de 0 au i-ième chiffre $ V_i $ est $ V_i = \sum^i_{k = 0} d_i \times 10^i $ Il peut être trouvé par. Le reste $ s_i $ obtenu en divisant ce nombre par p est $ s_i = (\sum^i_{k = 0} m_i) \% p $ Il peut être trouvé par. Écrivons ceci en quelques colonnes. $ S = [s_N, s_{N - 1}, \cdots, s_1, s_0]$ Si vous coupez l'intervalle où ce $ s_i $ correspond, ce sera une valeur qui peut être divisée par $ p $. Il suffit donc de compter le nombre de combinaisons. De plus, puisque les chiffres qui satisfont $ s_i = 0 $ sont divisibles tels quels, le nombre est également compté.

(ii) Lorsque $ p = 2, 5 $

Le nombre divisible par 2 et le nombre divisible par 5 peuvent être déterminés en ne regardant que le dernier chiffre. Il peut être obtenu en additionnant toutes les combinaisons possibles (n façons si le nombre est le nième chiffre à partir de la gauche) lorsque le nombre qui satisfait la condition est mis au 1er chiffre.

Cependant, pour rendre cela encore plus rapide, la loi de distribution du calcul résiduel

ab \mod c = (a \mod c)(b\mod c)\mod c

Est également utilisé pour calculer le reste pour 10 $ ^ i $. Je n'ai pas remarqué cela (ou parce que je ne connaissais pas la loi du calcul du surplus), et même en regardant les exemples de réponses d'autres personnes, TLE s'est produit fréquemment.



n, p = map(int,input().split())
D = input()
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

Pour le moment, je terminerai l'article jusqu'à présent. Si j'ai le temps, j'aimerais également ajouter la question F.