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

Temps requis

スクリーンショット 2020-04-02 18.52.21.png

Impressions

Étant donné que j'y étais auparavant, c'est la question à venir. Je peux répondre complètement si c'est à ce niveau, mais je veux être capable de rivaliser fermement avec quelque chose à un niveau légèrement supérieur.

Problème A

Notez qu'il faut que a <= x ainsi que a + b> = x.

answerA.py


a,b,c,d=[int(input()) for i in range(4)]
print(min(a,b)+min(c,d))

Problème B

Considérez le nombre de cabines de péage pour 1 ~ x et x ~ n respectivement. Si vous comptez le nombre de cabines de péage de 1 à x, vous pouvez également trouver le nombre de cabines de péage de x à n.

answerB.py


n,m,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in a:
    if i<x:
        ans+=1
    else:
        break
print(min(ans,m-ans))

Problème C

Concernant la valeur médiane, puisque n est un nombre pair, le n // 2e nombre ou le n // 2 + 1er nombre sera la valeur médiane lorsque les nombres 1 à n sont numérotés par ordre croissant. Si le n // 2e nombre est omis du 1er, le n // 2 + 1e nombre sera la valeur médiane, et si le n // 2 + 1er au nième nombre est omis, n /// Le deuxième nombre est la médiane. (** J'ai fait une expérience et je l'ai confirmée. **)

answerC.py


n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
k,l=y[n//2-1],y[n//2]
for i in range(n):
    if x[i]<=k:
        print(l)
    else:
        print(k)

Problème D

Premièrement, pour $ \ _ {a_i} C \ _ {a_j} $, il est clair que lorsque vous corrigez ** $ a \ _j $, plus $ a \ _i $ est grand, plus gros **. Par conséquent, ** $ a \ _i $ est déterminé comme étant le plus grand de a **, il est donc seulement nécessaire de déterminer une variable de ** $ a \ _j $ **. Par conséquent, si vous calculez les éléments d'un autre que max (a) comme $ a_j $ dans $ \ _ {max (a)} C \ _ {a_j} $ et comparez leurs grandeurs, la valeur maximale est O (n). Il y a un piège ici, bien qu'il semble être recherché. En effet, ** $ \ _ {max (a)} C \ _r $ ne peut pas être calculé avec O (1) **. De plus, si vous créez un tableau pour le calcul de combinaison, il sera calculé par O (1), mais il faudra O (n) pour préparer le tableau, donc il ne sera pas à temps (n est jusqu'à 10 $ ^ 9 $). Par conséquent, si vous calculez $ \ _ {max (a)} C_r $, vous constaterez que vous ne pouvez pas respecter le délai. Maintenant, pensons à trouver $ a_j $ quand ** $ \ _ {max (a)} C \ _ {a_j} $ est le maximum sans calculer **. Ensuite, vous pouvez voir que $ a_j $ est maximisé aussi près de n / 2 que possible (je vais omettre la preuve car c'est un problème, mais c'est difficile à prouver en utilisant $ \ _nC \ _r = \ _nC \ _ {nr} $ Ça ne ressemble pas à ça.) Par conséquent, la réponse est l'élément d'un max (a) excluant qui est le plus proche de max (a) / 2. Cela nous a permis de trouver $ \ _nC \ _r $ sans le calculer. Après avoir implémenté ce qui précède, le code est le suivant.

answerD.py


n=int(input())
a=sorted(list(map(int,input().split())))
b=a[n-1]
a.pop(n-1)
ans=0
for i in range(n-1):
    if abs(b/2-a[ans])>abs(b/2-a[i]):
        ans=i
print(str(b)+" "+str(a[ans]))

Recommended Posts

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 127 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 123 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 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
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