Les résultats de cette fois

Impressions de cette époque

Cette fois, je l'ai résolu sans aucune concentration et sans considération appropriée, j'ai donc mis à jour le classement le plus bas de tous les temps et obtenu la performance la plus basse en 2020. Je pense que le problème E aurait pu être résolu si j'avais utilisé correctement ma tête, et je sens que D manquait également de considération. (Parce que mon mental s'est effondré en chemin ...) Mais pour être honnête, je ne sais pas trop quoi changer pour augmenter le tarif ... Pour le moment, je pense qu'il n'y a pas d'autre choix que de résoudre divers problèmes et de laisser les motifs typiques s'imprégner dans le corps ...

Problème A

J'étais impatient, donc je suis gêné de le résoudre de façon folle à partir de maintenant.

`A.py`


n=int(input())
if n%1000==0:
    print(0)
else:
    print(1000-n%1000)

Problème B

C'est un problème que je n'aime pas vraiment car des erreurs de frappe sont susceptibles de se produire. Cependant, je pense que je pourrais mieux l'écrire, donc je le regrette.

`B.py`


n=int(input())
d={"AC":0,"WA":0,"TLE":0,"RE":0}
for i in range(n):
    d[input()]+=1
print("AC x "+str(d["AC"]))
print("WA x "+str(d["WA"]))
print("TLE x "+str(d["TLE"]))
print("RE x "+str(d["RE"]))

Problème C

Cette fois, une recherche complète a été lancée en raison du problème C. Je veux réfléchir à la façon de sélectionner les lignes et les colonnes à peindre en rouge, alors copiez la matrice qui a été entrée en premier, écrasez-la avec du rouge (x) et comptez enfin le nombre de noir (#) qui reste. Comme je l'ai remarqué en écrivant ce commentaire, il est facile à mettre en œuvre si vous ne vous souciez pas de copier et de compter les lignes et les colonnes spécifiées, je suis fou depuis le premier problème de base. peut être.

`C.py`


h,w,K=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for i in range(2**h):
    for j in range(2**w):
        d=[[c[z][v] for v in range(w)]for z in range(h)]
        for k in range(h):
            if (i>>k)&1:
                for l in range(w):
                    d[k][l]="x"
        for k in range(w):
            if (j>>k)&1:
                for l in range(h):
                    d[l][k]="x"
        cnt=0
        for k in range(h):
            for l in range(w):
                cnt+=(d[k][l]=="#")
        ans+=(cnt==K)
print(ans)

Problème D

Pour une preuve détaillée, reportez-vous à Explication, et voici une explication sensuelle.

Tout d'abord, il semble qu'il vaut mieux arriver dans l'ordre de la personne la plus sympathique **, car la situation ne s'améliore pas même si la personne la moins sympathique arrive en premier.

De plus, sous cette hypothèse, vous pouvez penser à la ** méthode de la cupidité **, qui est la plus grande position que vous devriez interrompre. Autrement dit, vous pouvez interrompre comme suit:

Dans la figure ci-dessus, la gentillesse de la personne est écrite sur le côté gauche et le confort est écrit sur le côté droit. Vous pouvez voir que $ A_i $ obtient la convivialité de $ A_ {[\ frac {i + 1} {2}]} $ lors d'une interruption comme celle-ci (pensez-y comme une dichotomie complète). pense.). Si vous remarquez jusqu'à présent, la mise en œuvre est facile et ce sera comme suit.

Je pensais que je n'étais pas gourmand, alors je l'ai jeté, mais je veux garder à l'esprit que les bases sont gourmandes.

`D.py`


n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
for i in range(1,n):
    ans+=a[i//2]
print(ans)

E problème

L'idée de base n'est pas difficile, mais il y a tellement de boîtiers d'angle que c'était un sérieux problème en termes de montage.

Je ne pouvais pas travailler sur l'implémentation parce que je pensais que ce serait plus facile pour moi d'y réfléchir, mais quand j'ai vu la réponse, j'ai senti que je manquais encore de compétences parce que c'était écrit de manière soignée. ** Je veux acquérir la capacité de réfléchir fermement aux cas **.

Tout d'abord, considérons le cas où le produit des nombres ** $ K $ est un nombre négatif, en notant qu'il y a peu de modèles qui sont négatifs **. Ensuite, le produit des nombres ** $ K $ sera négatif lorsque seul un nombre impair de nombres $ K $ peut être sélectionné **. Ici, s'il y a un ou plusieurs nombres supérieurs ou égaux à 0, vous pouvez contrôler le nombre pair / impair du nombre de nombres négatifs inclus dans le nombre $ K $ selon que le nombre est inclus ou non. Par conséquent, le produit des nombres $ K $ est négatif lorsque tous les nombres $ N $ donnés sont négatifs et que $ K $ est impair (①), et $ N = K $ et donné. Si le nombre de $ N $ comprend un nombre impair de nombres négatifs (②), ce sera l'un ou l'autre.

Prise en compte de ① ↓ Il n'est pas difficile de calculer quand le nombre donné de $ N $ est entièrement négatif ou est égal à 0 ou plus, j'ai donc essayé de les calculer tous ensemble. Autrement dit, lorsque le nombre donné de $ N $ est tout négatif, si $ K $ est pair, le produit est positif, donc le produit de $ K $ est le plus grand dans l'ordre de celui avec la plus grande valeur absolue, et $ Si K $ est impair, le produit est négatif, donc le produit de $ K $ est le plus grand par ordre croissant de valeur absolue. De plus, lorsque tous les nombres sont égaux à 0 ou plus, le produit de $ K $ est le maximum dans l'ordre de celui avec la plus grande valeur absolue.

Mise en œuvre de ① ↓ Stocke les nombres supérieurs ou égaux à 0 dans ʻap, stocke les nombres négatifs dans ʻam, et $ N $ if len (ap) == 0 ou len (am) == 0 Sont tous des nombres négatifs (ou tous des nombres positifs), donc implémentez comme considéré. De plus, ʻap et ʻam sont triés par ordre décroissant de valeurs absolues.

Prise en compte et mise en œuvre de ② ↓ Si $ N = K $, considérons le produit des nombres $ N $ donnés. Ceci est demandé immédiatement après réception de l'entrée.

Sur la base de ce qui précède, nous considérerons la politique sous ** où la valeur maximale du produit de nombres $ K $ est garantie d'être égale ou supérieure à 0 **. (J'étais confus dans ce domaine parce que j'étais confus au sujet de la politique.)

Premièrement, le produit de $ K $ ne sera pas égal ou supérieur à 0 sauf si ** le nombre de nombres négatifs est pair **, le produit est donc calculé par appariement ** dans l'ordre à partir du nombre avec la plus grande valeur absolue. Aussi, afin de sélectionner un nombre négatif et un nombre supérieur ou égal à 0, le produit est calculé en appariant le nombre supérieur ou égal à 0 dans l'ordre décroissant, et ceux-ci sont stockés dans «apm2» dans l'ordre décroissant. (Après cela, je veux vérifier combien de nombres sont 0 ou plus, donc marquez 1 pour les nombres 0 ou plus et 0 pour les nombres négatifs.)

Ici, lors de l'appariement, il est possible qu'il reste un nombre négatif et un nombre supérieur ou égal à 0, mais si vous choisissez un nombre négatif, vous n'avez pas besoin de le choisir car le produit sera négatif, alors choisissez un nombre positif. Veuillez noter qu'il existe une possibilité.

Premièrement, quand ** $ K $ est pair **, vous pouvez trouver le produit de $ [\ frac {k} {2}] $ nombres d'avant ʻapm2`, mais ** $ K $ est Pour les nombres impairs **, vous devez sélectionner un autre nombre en plus du nombre $ [\ frac {k} {2}] $. À ce stade, si vous sélectionnez "Sélectionnez l'un des plus grands nombres positifs qui n'ont pas encore été sélectionnés (✳︎1)", ce n'est pas optimal dans les cas suivants.

5 3
-5 -1 1 2 3

Dans le cas ci-dessus, -5, -1,3 est le meilleur, mais selon (✳︎1), 1,2,3 est le meilleur. En d'autres termes, il peut être optimal de "choisir la plus grande paire de nombres positifs sélectionnés, sauf pour le plus petit nombre, qui n'est pas sélectionné par ʻapm2` (✳︎2)". (** Assurez-vous de vérifier l'optimalité avec la méthode gourmande! **)

Par conséquent, tout en enregistrant l'index dans ʻap du nombre à sélectionner ensuite comme nombre positif dans p, d'abord ʻans le nombre de $ [\ frac {k} {2}] $ de l'avant. Je vais ajouter` (** Puisque l'opération à supprimer est gênante, j'ai essayé de la stocker dans le tableau une fois sans demander le produit **).

Sous ceci, si $ K $ est pair, trouvez le produit de tous les nombres de ʻans, et si $ K $ est impair, suivez (✳︎1) et (✳︎2) ci-dessus, ʻap [ Soit lors de la sélection de p] (①), soit lors de la sélection de ʻapm2 [k // 2] [0]sauf pour ʻap [p-1](②).

Ici, quand p == len (p), tous les nombres au-dessus de 0 sont épuisés, donc il n'y a pas de nombre correspondant à p, et le motif ① n'existe pas. De plus, lorsque p == 0, aucun ensemble de nombres supérieurs ou égaux à 0 n'a encore été utilisé, donc le motif (2) n'existe pas. (** N'oubliez pas de considérer les exceptions! **)

Une mise en œuvre minutieuse de ce qui précède entraînerait: Nous avons également défini une fonction (multarray) pour trouver le produit d'un tableau donné divisé par 10 $ ^ 9 + 7 $ pour simplifier l'implémentation.

`E.py`


#x:Tableau
mod=10**9+7
def multarray(x):
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

n,k=map(int,input().split())
a=list(map(int,input().split()))

#n==Dans le cas de k, il suffit d'appeler
if n==k:
    print(multarray(a))
    exit()

#Stocké séparément pour les nombres supérieurs ou égaux à 0 et les nombres négatifs
ap,am=[],[]
for i in range(n):
    if a[i]>=0:
        ap.append(a[i])
    else:
        am.append(a[i])
#Trier par valeur absolue
ap.sort(reverse=True)
am.sort()

#Si seul le nombre est égal ou supérieur à 0 ou seulement le nombre positif, le cas est divisé en premier.
if len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[:k]))
    else:
        print(multarray(am[::-1][:k]))
    exit()

#Stocker par paires(Enregistrez si c'est 0 ou plus ou négatif)
apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)

#Vérifiez où chercher ensuite avec un nombre supérieur ou égal à 0
p=0
ans=[]
for i in range(k//2):
    p+=(2*apm2[i][1])
    ans.append(apm2[i][0])

#Quand K est pair
if k%2==0:
    print(multarray(ans))
    exit()

ans_cand=[]
#Lors de l'ajout d'un
if p!=len(ap):
    ans_cand.append(multarray(ans)*ap[p]%mod)
#En réduisant un et en augmentant deux
if p!=0:
    #Diminuer l'indice
    check_i=ans.index(ap[p-1]*ap[p-2])
    #ap[p-1]Opération pour réduire(Évitez la division 0)
    ans[check_i]=ap[p-2]
    ans.append(apm2[k//2][0])
    ans_cand.append(multarray(ans))
print(max(ans_cand))

Problème F

Je ne l'ai pas encore résolu. Je publierai bientôt un commentaire.

[PYTHON] AtCoder Débutant Contest 173 Critique