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

Temps requis

Impressions

A partir de ce moment, j'ai commencé à utiliser la fonction Bachacon d'AtCoder Problems! (Parce que la performance estimée sort) Quand je l'ai résolu une fois auparavant, je ne pouvais pas du tout rivaliser avec le problème D et je ne l'ai pas examiné, mais j'ai résolu le problème similaire en douceur parce que je l'avais déjà résolu. Pour le problème D, il est bon d'être conscient du chiffre DP, mais je sens que j'ai beaucoup appris.

Problème A

Vous pouvez le multiplier par 1 / t.

answerA.py

t,x=map(int,input().split())
print(t/x)

Problème B

Comparez la somme du côté le plus long et des autres côtés.

answerB.py

n=int(input())
l=sorted(list(map(int,input().split())))
print("Yes" if l[-1]<sum(l[:-1]) else "No")

Problème C

Lorsque n> = m, vous pouvez placer des pièces en tous points sans bouger, donc ce sera 0. Lorsque n <m, sélectionnez la cellule où chaque image peut être placée, mais lors de l'expérimentation, on suppose qu'entre $ X_i $ et $ X_ {i + 1} $ ($ X_i $ est trié par ordre croissant) Quand.) Vaut $ Y_i $, vous pouvez visiter tous les carrés en sélectionnant mn différents $ Y_i $ (inversement, même si vous sélectionnez moins que ce nombre de $ Y_i $, tous Je ne peux pas visiter la messe.) Par conséquent, vous pouvez sélectionner le plus petit m-n de $ Y_i $ et afficher le total. Ce problème est un modèle courant et doit être maîtrisé. (Il est important que ** ce soit une section que vous passez en déplaçant ** et que ** vous puissiez choisir librement la section **.)

answerC.py

n,m=map(int,input().split())
x=sorted(list(map(int,input().split())))
y=sorted([x[i+1]-x[i] for i in range(m-1)])
if n>=m:
    print(0)
else:
    print(sum(y[:m-n]))

Problème D

Je pense que c'est un problème avec un effet d'apprentissage élevé car il est nécessaire de connaître les caractéristiques de XOR tout en incluant l'idée très fréquente de chiffre DP de motifs de ** K ou moins **. L'idée de base du chiffre DP etc. peut être facilement comprise en regardant l'article de Kenchon. Ci-dessous, j'expliquerai en incluant mes propres points de vue.

Tout d'abord, faites attention à chaque chiffre qui est la base de XOR (c'est un chiffre en binaire. Veuillez noter que le chiffre ci-dessous est un chiffre en binaire). À ce stade, envisagez de ** maximiser chaque chiffre **, mais le i-ème chiffre de $ X \ XOR \ A_k $ (k = 1 ~ N) est 0 ou 1, et le i de $ A_k $ Lorsque le chiffre est 0, le i-ème chiffre de X est 1 et lorsque le i-ème chiffre de $ A_k $ est 0, le i-ème chiffre de X peut être mis à 1 pour maximiser le chiffre (1). Je vais. Par conséquent, comptez si le i-ième chiffre de $ A_1 $ ~ $ A_N $ est 0 ou 1, et s'il y a beaucoup de ** 0, définissez le i-ème chiffre de X à 1 et s'il y en a plusieurs, définissez le i-ème chiffre de X à 0. ** est le cas où la somme de $ X \ XOR \ A_1 $ ~ $ X \ XOR \ A_N $ dans le i-ième chiffre est maximisée. Cependant, il existe également une condition de 0 ou plus et de K ou moins ici, nous allons donc considérer cette condition à partir d'ici. Considérant le cas où il est inférieur ou égal à K, c'est ** en comptant à partir du chiffre supérieur, le i-ème chiffre est égal à K et le i + 1-ème chiffre est plus petit que K ** (ceci). C'est l'idée du chiffre DP des motifs inférieurs à K!). Notez également que chaque chiffre est ici 0 ou 1.

Tout d'abord, étant donné que 0 et 1 peuvent être pris après le chiffre i + 1, vérifiez avec la variable de contrôle si 0 et 1 peuvent être pris (initialiser avec False au début). De plus, soit X (X = 1 ~ K) le nombre qui maximise f. Ici, si le jème chiffre est 1 lorsque l'on regarde K à partir du chiffre supérieur, X peut prendre à la fois 0 et 1. De plus, si le jème chiffre de X prend 0, alors le jème chiffre de X est plus petit que K, de sorte que les chiffres suivants peuvent prendre 0 ou 1 librement (régler check sur True). ). Au contraire, si le jème chiffre de K est 0, prendre 1 sera plus grand que K, donc seul 0 peut être pris quel que soit le jème chiffre de $ A_1 $ ~ $ A_N $ (où check est Vrai). Dans ce cas, vous pouvez choisir librement 0 ou 1). (↑ ** Cette opération est également utilisée pour les chiffres DP avec des restrictions de K ou moins, j'ai donc pensé qu'elle devrait être familière **.

Vous pouvez trouver la réponse en mettant en œuvre l'idée ci-dessus et en ajoutant la valeur maximale (possible en dessous de K) dans chaque chiffre à ans.

answerD.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
co=[0]*50
check=False
for i in range(49,-1,-1):
    for j in range(n):
        if (a[j]>>i)&1:
            co[i]+=1
    if (k>>i)&1:
        if co[i]>=n-co[i]:
            ans+=(co[i]*(2**i))
            check=True
        else:
            ans+=((n-co[i])*(2**i))
    else:
        if check:
            if co[i]>=n-co[i]:
                ans+=(co[i]*(2**i))
            else:
                ans+=((n-co[i])*(2**i))
        else:
            ans+=(co[i]*(2**i))
print(ans)