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

Questions passées résolues pour la première fois

Temps requis

Problème A

Je pensais que c'était ennuyeux selon que c'était la même chose ou non, mais la réponse était plus intelligente.

answerA.py

x=[1,3,5,7,8,10,12]
y=[4,6,9,11]
z=[2]

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

if (a in x and b in x) or (a in y and b in y) or (a in z and b in z):
    print("Yes")
else:
    print("No")

amswerA_better.py

xyz=[0,2,0,1,0,1,0,0,1,0,1,0]
a,b=map(int,input().split())
print("Yes" if xyz[a-1]==xyz[b-1] else "No")

Problème B

Ajoutez "#" selon le cas

answerB.py

h,w=map(int,input().split())
hw=["#"*(w+2)]
for i in range(h):
    hw.append("#"+input()+"#")
hw.append("#"*(w+2))
for i in range(h+2):
    print(hw[i])

Problème C

Même si c'était un problème C, c'était difficile, mais la difficulté était bleu clair. Quand je l'ai recherché, c'était le deuxième plus lent des codes AC, mais j'aime personnellement ce code boueux. (J'ai essayé de l'écrire, mais c'était un code assez terrible. Je le regrette.) Premièrement, quand il était divisible par 3, il produisait 0, mais ce n'est pas nécessaire. Dans l'instruction else, il existe une méthode pour créer un rectangle horizontalement long avec la première instruction for et pour diviser autant que possible le rectangle restant en deux parties égales, il existe donc une méthode pour le diviser verticalement et horizontalement. J'ai écrit toutes les zones du rectangle qui semblent se faire sentir. (J'ai remarqué en examinant que ** il y a beaucoup de duplication et beaucoup de traitements inutiles **.) La seconde consiste à créer un rectangle verticalement long et à effectuer le même traitement. En outre, le deuxième code est une amélioration. Le processus d'amélioration est comme ça. (J'efface la partie rouge parce que je n'en ai pas besoin.) (Le bas est le premier code.)

answerC.py

h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    x=[]
    for i in range(1,w):
        sub=[]
        sub.append([h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)])
        sub.append([h*i,h*((w-i)//2+1),h*(w-i)-h*((w-i)//2+1)])
        sub.append([h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)])
        sub.append([h*i,(w-i)*(h//2+1),h*(w-i)-(w-i)*(h//2+1)])
        for j in sub:
            x.append(max(j)-min(j))
    for i in range(1,h):
        sub=[]
        sub.append([w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)])
        sub.append([w*i,w*((h-i)//2+1),w*(h-i)-w*((h-i)//2+1)])
        sub.append([w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)])
        sub.append([w*i,(h-i)*(w//2+1),w*(h-i)-(h-i)*(w//2+1)])
        for j in sub:
            x.append(max(j)-min(j))
    print(min(x))

answerC_better.py

h,w=map(int,input().split())
x=[]
for i in range(1,w):
    x1=[h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)]
    x2=[h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)]
    x.append(min(max(x1)-min(x1),max(x2)-min(x2)))
for i in range(1,h):
    x1=[w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)]
    x2=[w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)]
    x.append(min(max(x1)-min(x1),max(x2)-min(x2)))
print(min(x))

Problème D

La première moitié des N éléments de a'composent les 2N premiers éléments, et la seconde moitié des N éléments de a'composent les 2N derniers éléments. Ici, lorsque 2N éléments sont sélectionnés comme a 'et que les N éléments de la première moitié et de la seconde moitié sont considérés, le dernier élément de la première moitié est considéré comme le k (N <= k <= 2N) ème élément de l'original a. Lorsque vous le faites, vous pouvez également voir que le kth et le plus tôt sont inclus dans la première moitié de a ', et le kth et les suivants sont inclus dans la dernière moitié de a'. De plus, afin de maximiser (la somme des N éléments de la première moitié de a ') - (la somme des N éléments de la seconde moitié de a'), la somme des N éléments de la première moitié de a 'est maximisée. Puisqu'il est seulement nécessaire de le minimiser, les premières moitiés de k pièces sont triées par ordre décroissant et la somme de N éléments est considérée de l'avant, et les dernières moitiés de 3N-k pièces sont triées par ordre croissant et la somme des N éléments est considérée de l'avant. est. Cependant, si vous déplacez simplement k et y réfléchissez, ce sera la quantité de calcul de O (N * N * logN) et ce sera TLE. J'ai donc pensé à ce qui se passerait si j'augmentais k. Nous avons utilisé une méthode pour classer si l'élément nouvellement ajouté est plus petit que le plus petit élément lorsqu'il est incrémenté, et mettre à jour la somme si elle n'est pas ajoutée si elle est petite et si elle est grande, mais cette méthode est le plus petit élément. C'était compliqué de sauvegarder quelque chose et de le comparer un par un (la somme des N éléments dans la première moitié de a 'est considérée ici). Ce que j'aurais dû proposer ici, c'est l'utilisation de ** Priority_queue **. Quand vous y réfléchissez plus tard, il y a de nombreux points évidents. En effet, Priority_queue ** vous permet de récupérer des éléments de haute priorité en heures de journalisation et de pousser la vitesse en heures de journal **. Pourquoi n'avez-vous pas décidé d'utiliser Priority_queue lorsque vous essayez de ** séparer les cas avec le plus petit (ou maximum) comme limite **? regrettant. Une fois que j'ai établi une politique, j'ai pu faire un panoramique, Priority_queue est génial. Je n'ai pas beaucoup utilisé le tas de Python parce que j'utilise souvent la file d'attente Priority_ de C ++, mais je me demande si je peux changer la priorité comme C ++ n'est-ce pas gênant? J'essaierai de savoir ce que je peux faire si j'en ai envie (je ne veux pas le faire parce que c'est un problème si je dois en créer un nouveau dans la classe).

answerD.py

import heapq

n=int(input())
a1=[]
b1=[]
a2=[]
b2=[]
s=input().split()
for i in range(3*n):
    if i<n:
        a1.append(int(s[i]))
    elif i>=2*n:
        b1.append(-int(s[i]))
    else:
        a2.append(int(s[i]))
        b2.append(-int(s[3*n-i-1]))
suma=[sum(a1)]
sumb=[sum(b1)]
heapq.heapify(a1)
heapq.heapify(b1)

for i in range(0,n):
    heapq.heappush(a1,a2[i])
    k=heapq.heappop(a1)
    l=suma[-1]
    suma.append(l+a2[i]-k)
for i in range(0,n):
    heapq.heappush(b1,b2[i])
    k=heapq.heappop(b1)
    l=sumb[-1]
    sumb.append(l+b2[i]-k)

ma=-1000000000000000
for i in range(n+1):
    ma=max(ma,suma[i]+sumb[-i-1])
print(ma)