Daily AtCoder # 52 en Python

introduction

Dernière fois Aujourd'hui, je vais résoudre 3 questions d'AGC-A.

** Pensées ** J'ai compris l'idée, mais je n'ai pas pu la mettre en œuvre. Soit $ a $ une liste de $ [0] * (n + 1) $. Je n'ai pas pu l'implémenter car j'essayais de gérer à la fois «<» et «>» ensemble. N est également d'environ 5 $ * 10 ^ 5 $, donc $ O (2N) (le montant du calcul ignore le coefficient) $ passera. Commencez par traiter à partir de «<». Si $ s [i] == '<' $, alors $ a [i + 1] $ devient $ a [i] + 1 $. Ensuite, nous traiterons '>', mais une certaine ingéniosité est requise. '>' Doit être calculé à partir de l'arrière en raison de l'inégalité. Donc, multipliez la plage (n) par l'inverse. Si $ s [i] == '>' $, prenez $ a [i] = max (a [i + 1] + 1, a [i]) $. Enfin, prenez $ sum (a) $.

s = list(input())
n = len(s)

a = [0] * (n+1)
for i in range(n):
    if s[i] == '<':
        a[i+1] = a[i]+1
for i in reversed(range(n)):
    if s[i] == '>':
        a[i] = max(a[i+1]+1,a[i])
print(sum(a))

AGC015-A

** Pensées ** Puisque $ N = 10 ^ 9 $, $ O (N) $ ne passera pas. $ n = 1 $ → 1 si $ a = b $, 0 si $ a \ neq b $. De plus, il vaut 0 lorsque $ a $> $ b $ et 1 lorsque $ a $ = $ b $. Considérez les autres cas. La somme minimale n'est pas quand $ a * n $. C'est parce que la valeur maximale n'atteint pas $ b $ quand tout est $ a $. Par conséquent, il devient $ a (n-1) + b $. De même, la somme maximale est $ b (n-1) + a $. Vous pouvez tout faire de $ a (n-1) + b $ à $ b (n-1) + a $. Par conséquent, le nombre de sommes est $ b (n-1) + a- {a (n-1) + b} + 1 $. Si vous calculez cela, vous pouvez le transformer en $ (b-a) (n-2) + 1 $. Il peut être calculé sans transformer la formule, mais il a été transformé car il devrait être propre.

n, a, b = map(int,input().split())

if n == 1:
    if a == b:
        print(1)
    else:
        print(0)
elif a >= b:
    if a == b:
        print(1)
    else:
        print(0)
else:
    ans = (b-a)*(n-2)+1
    print(ans)

AGC006-A

** Pensées ** Puisque $ N $ est assez petit, recherchez $ N $ dans l'ordre dans une tranche de $ s ou t $ pour trouver la valeur maximale qu'il contient dans l'autre.

n = int(input())
s = input()
t = input()

c = 0
for i in range(n):
    d = t[:i]
    if d in s:
        c = i
if s == t: #Vous pouvez écrire plus tôt et ignorer le processus pour
    print(n)
else:
    print(2*n-c)

Résumé

Pourquoi AGC-A a-t-il une impression difficile? Il sera marron à l'ABC de cette semaine. A bientôt, bonne nuit.