[PYTHON] AtCoder Beginner Contest 082 Revue des questions précédentes

Temps requis

Impressions

J'ai pu terminer le bachacon à la troisième place, probablement parce que je me sentais mieux. Cependant, la dernière question n'était pas prouvée et je l'ai passée d'une manière légèrement différente de la réponse, je voudrais donc revoir la réponse fermement.

Problème A

Continuez. Je n'ai pas utilisé math.ceil à cause de l'erreur. Je n'ai pas envie d'utiliser math.ceil pour l'avenir.

answerA.py

a,b=map(int,input().split())
print(-((-a-b)//2))

Problème B

Pensez simplement à la taille du trié. Je comparais avec désinvolture la taille de la liste, mais ** la comparaison de taille de la liste fonctionne de la même manière que la comparaison de taille de la chaîne de caractères **, n'est-ce pas?

answerB.py

s,t=sorted(list(input())),sorted(list(input()),reverse=True)
print("Yes" if s<t else "No")

Problème C

De plus, j'ai été surpris parce que j'avais un problème avec la fonction groupby. Ancien problème Est-il trop difficile d'utiliser la fonction groupby? ?? Divisez en groupes par nombre et supprimez tout s'il y en a moins que ce nombre, et s'il y en a plus que ce nombre, supprimez jusqu'à ce qu'ils soient le même nombre.

answerC.py

n=int(input())
a=sorted(list(map(int,input().split())))

def groupby():
    global a
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

b=groupby()
ans=0
for i in b:
    if i[0]>i[1]:
        ans+=i[1]
    else:
        ans+=(i[1]-i[0])

print(ans)

Problème D

Tout d'abord, considérez ** le type de comportement que le robot montrera en F et T, respectivement **. Tout d'abord, F est facile. Lorsqu'il y a k F consécutifs, il avancera de k dans la direction qui fait face à ce moment. Au contraire, et s'il y a k T consécutifs? Pour le moment, jusqu'où vous allez ne change pas, mais la direction change. Notez qu'il n'y a que quatre directions, et si les directions sont différentes de 180 degrés, on peut dire que le positif et le négatif sont différents dans le même sens. En d'autres termes, ** à la fin, il s'avère qu'il n'y a que deux directions **, et si vous dessinez une petite figure et y réfléchissez, ** la direction ne change pas lorsque k est pair, et la direction change lorsque k est impair **. compris. De ce qui précède, nous pouvons voir la distance parcourue par chaque F continu sur l'axe des x ou sur l'axe des y. De plus, puisque la direction de l'axe x et la direction de l'axe y peuvent être considérées indépendamment, nous considérerons ** ce qui arrive à la direction de l'axe x ** ci-dessous. La prochaine chose à considérer est que lorsque le robot avance $ f_1, f_2,…, f_k $ k fois dans la direction de l'axe des x, décidez s'il faut rendre chaque positif ou négatif ($ 2 ^ k $ way) et additionnez simplement le total. La question est de savoir si cela peut être x. Ici, j'ai trié $ f_1, f_2,…, f_k $ par ordre décroissant et sélectionné positif ou négatif pour que le plus grand f soit aussi proche de x que possible. Cependant, cela n'a pas été prouvé, nous devons donc le faire de manière prouvable (je ne sais pas pourquoi cela a été fait de cette façon). Ici, nous avons dû ** utiliser ** DP, en notant que c'était 2 $ ^ k $. Autrement dit, de- (valeur absolue de $ f_1, f_2,…, f_k $) à la valeur absolue de $ f_1, f_2,…, f_k $, sélectionnez $ f_1, f_2,…, f_k $ dans l'ordre et DP Vous avez juste à faire. On peut dire que le robot peut atteindre les coordonnées (x, y) s'il peut être réglé sur x comme décrit ci-dessus et que la coordonnée y peut également être réglée sur y. En outre, le deuxième code était le plus rapide du code de PyPy.

answerD.py

from sys import exit
s=input()
x,y=map(int,input().split())

def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2
s=groupby(s)
a,b=[],[]
turn=True
#Si tout droit au début
if s[0][0]=="F":
    x-=s[0][1]
    s.pop(0)
for i in s:
    if i[0]=="F":
        if turn:
            a.append(i[1])
        else:
            b.append(i[1])
    else:
        if i[1]%2==1:
            turn=not turn
a.sort(reverse=True)
b.sort(reverse=True)
for i in a:
    if x>0:
        x-=i
    else:
        x+=i
for i in b:
    if y>0:
        y-=i
    else:
        y+=i
if x!=0 or y!=0:
    print("No")
else:
    print("Yes")

answerD_faster.py

def main():
    from sys import exit
    s=input()
    x,y=map(int,input().split())

    def groupby(a):
        a2=[[a[0],1]]
        for i in range(1,len(a)):
            if a2[-1][0]==a[i]:
                a2[-1][1]+=1
            else:
                a2.append([a[i],1])
        return a2

    s=groupby(s)
    a,b=[],[]
    turn=True
    #Si tout droit au début
    if s[0][0]=="F":
        x-=s[0][1]
        s.pop(0)
    for i in s:
        if i[0]=="F":
            if turn:
                a.append(-i[1])
            else:
                b.append(-i[1])
        elif i[1]%2==1:
            turn=not turn
    a.sort()
    b.sort()
    for i in a:
        x=abs(x)-abs(i)
    if x!=0:
        print("No")
        exit()
    for i in b:
        y=abs(y)-abs(i)
    if y!=0:
        print("No")
        exit()
    print("Yes")
main()