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

Temps requis

スクリーンショット 2020-04-14 18.19.47.png

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)

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 085 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 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 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 103 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 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 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 071 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