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

Temps requis

Impressions

Bien que la résolution du problème C ait été un problème, j'ai pu le résoudre avec une solution simple, j'ai donc ressenti le manque de concentration dans le bachacon. De plus, j'affiche la formule entourée de $, mais pour une raison quelconque, un saut de ligne est inséré. Je vous serais reconnaissant de bien vouloir me dire comment y faire face. → Concernant ce problème, il semble qu'un problème puisse survenir lors de l'utilisation de la barre inférieure (_). (29/04/2020)

Problème A

Je ne savais pas si c'était 2019 ..., mal lu ... Si vous utilisez le fractionnement, vous pouvez le fractionner avec une barre oblique inverse.

answerA.py

s=list(map(int,input().split("/")))
if s[0]<2019:
    print("Heisei")
elif s[0]>2020:
    print("TBD")
else:
    print("TBD" if s[1]>4 else "Heisei")

answerA_better.py

s=list(map(int,input().split("/")))
print("TBD" if s[1]>4 else "Heisei")

Problème B

Toutes les sommes doivent être prises en compte selon qu'elles sont des pièces de monnaie ou non.

answerB.py

n=int(input())
cnt=0.0
for i in range(n):
    x,u=input().split()
    x=float(x)
    cnt+=(x if u=="JPY" else x*380000.0)
print(cnt)

Problème C

C'était plus difficile que D (yeux blancs). ** Il est clair que vous pouvez essayer toutes les rues **, mais c'était difficile d'écrire toutes les rues, alors quand je réfléchissais à la façon de le concevoir, le temps passait énormément. Lorsque vous essayez le tout, notez d'abord que ** MP ne dépend que de la façon de choisir le bambou et non dans cet ordre **. Sur cette base, vous devriez penser à ** A, B, C quel bambou utiliser pour chaque ** (A, B, C, non utilisé). Answer a été implémenté de cette manière.) Tout d'abord, numérotez les n bambous originaux (correspondant à A à C) de 0 à 2 afin de déterminer quel bambou utiliser, A, B ou C (1). À ce stade, les bambous qui peuvent être utilisés (ou non) pour fabriquer chacun des bambous A, B et C ont été choisis. De plus, à ce stade, au moins un nombre de 0 à 2 doit apparaître, donc s'il n'y a pas de nombre, le processus passe à la boucle suivante (2). Sur cette base, nous examinerons quel bambou pour fabriquer chaque A, B, C, mais ** Sélectionnez un nombre quelconque de bambous pouvant être utilisés pour fabriquer chacun des A, B, C. Comme c'est bon, considérons un sous-ensemble ** par chaîne de bits (3). Cependant, dans ce cas également, si vous ne choisissez aucun bambou, nous ne le considérerons pas, nous le considérerons donc en excluant de tels cas (4). En pensant de cette manière, le MP requis pour déterminer les longueurs de A, B et C dans chaque cas peut être déterminé de manière unique (5), donc en considérant la valeur minimale pour chacun, le sujet Vous pouvez trouver le MP minimum. J'ai implémenté ce qui précède et c'est devenu comme suit, mais ** j'étais confus parce que j'étais trop mauvais pour nommer les variables ** et j'ai pu ** organiser la discussion ci-dessus dans mon esprit ** Il a fallu beaucoup de temps pour le résoudre. Je pense que je devrais l'écrire pour garder mon esprit organisé comme à chaque fois, mais quand je le résolve, je l'oublie. Je pensais que je n'avais pas d'autre choix que d'imprimer l'attitude en la résolvant à plusieurs reprises.

answerC.py

import itertools
n,*abc=map(int,input().split())
l=[int(input()) for i in range(n)]
inf=100000000000000
mi=inf
for i in list(itertools.product([i for i in range(3)],repeat=n)):#(1)↓
    sub=[[] for j in range(3)]
    for j in range(n):
        sub[i[j]].append(j)
    mi_sub=0
    for j in range(3):
        l_sub=len(sub[j])
        if l_sub==0:#(2)
            mi_sub=inf
            break
        mi_subsub=inf
        for k in range(2**l_sub):#(3)↓
            mi_subsubsub=[0,0]
            for l_subsub in range(l_sub):#(5)↓
                if ((k>>l_subsub) &1):
                    mi_subsubsub[0]+=1
                    mi_subsubsub[1]+=l[sub[j][l_subsub]]
            if mi_subsubsub[0]!=0:#(4)
                mi_subsub=min(mi_subsub,abs(mi_subsubsub[1]-abc[j])+mi_subsubsub[0]*10-10)
        mi_sub+=mi_subsub
    mi=min(mi,mi_sub)
print(mi)

itertools.product Une fonction qui peut générer un produit direct de plusieurs listes (vous pouvez écrire un itérateur multi-boucles de manière concise). En spécifiant plusieurs listes dans l'argument, un objet de type itertools.product est généré et renvoyé en tant que valeur de retour. Ensuite, en tournant l'instruction for, toutes les combinaisons peuvent être récupérées une par une (il est également possible de les lister). De plus, il est également possible de générer un produit direct de la même liste en spécifiant le nombre de répétitions en répétition, et dans ce problème, le produit direct est généré avec répétition = n pour la liste m.

Problème D

Au début, je pensais qu'il y avait une planification de section et une méthode d'imosu, mais j'ai pensé calmement et ce n'était pas le cas. Si vous considérez le problème en fonction du problème plutôt que de l'algorithme, vous ne serez pas accro au marais et vous pourrez réfléchir davantage. Maintenant, considérez quand vous étiez à un certain x. Alors x sera entouré de $ s_ {i-1} $, $ s_i $ et $ t_ {j-1} $, $ t_j $ ($ s_0 $, $ t_0 $) , $ s_ {a-1} $, $ t_ {b-1} $ est un peu différent s'il est à l'extérieur). A ce moment, le mouvement minimum est de se déplacer pour qu'il passe soit par le point $ s_ {i-1} $ ou $ s_i $ ou le point $ t_ {j-1} $ ou $ t_j $. Il est clair que la distance peut être atteinte (** dessinez un diagramme et réfléchissez-y avant de le remarquer **), vous pouvez donc vérifier les quatre façons de $ 2 \ times2 $ (et $ s_0 $, $ t_0 $, S'il est en dehors de $ s_ {a-1} $, $ t_ {b-1} $, il y a moins de points candidats à passer.). En outre, la plage de x peut être déterminée par la quantité de calcul logarithmique en utilisant la dichotomie, de sorte que le programme sera suffisamment rapide. Ceux-ci sont mis en œuvre comme suit: De plus, la distance parcourue sera plus courte si vous visitez à partir du plus proche des deux points sélectionnés.

answerD.py

a,b,q=map(int,input().split())
s=[int(input()) for i in range(a)]
t=[int(input()) for i in range(b)]
x=[int(input()) for i in range(q)]

from bisect import bisect_left

for i in range(q):
    y=bisect_left(s,x[i])
    z=bisect_left(t,x[i])
    k=([0] if y==0 else [a-1] if y==a else [y-1,y])
    l=([0] if z==0 else [b-1] if z==b else [z-1,z])
    mi=100000000000000
    for n in k:
        for m in l:
            if abs(s[n]-x[i])>abs(t[m]-x[i]):
                sub1,sub2=t[m],s[n]
            else:
                sub1,sub2=s[n],t[m]
            mi=min(mi,abs(sub1-x[i])+abs(sub2-sub1))
    print(mi)

Correction (03/05/2020)

Correction d'une erreur de lien.