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

Temps requis

スクリーンショット 2020-01-26 16.03.45.png

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.

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 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
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes