AtCoder Beginner Contest 082 Revue des questions précédentes

Temps requis

スクリーンショット 2020-03-26 19.41.37.png

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()

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 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 054 Revue des questions précédentes
AtCoder Beginner Contest 117 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 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
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes