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

Temps requis

スクリーンショット 2020-01-31 12.34.26.png

Impressions

D Problème de lecture erronée ... Le problème D était intéressant avec une nouvelle forme de DP, je l'aime beaucoup.

Problème A

Détermine si b% a vaut 0

answerA.py


a,b=map(int,input().split())
print(a+b if b%a==0 else b-a)

Problème B

J'ai passé trop de temps à l'implémenter ... Vous pouvez juger si tout le monde aime chacun des types m.

answerB.py


n,m=map(int,input().split())
x=[[int(j) for j in input().split()][1:] for i in range(n)]
cnt=0
for i in range(1,m+1):
    for j in range(n):
        if i not in x[j]:
            break
    else:
        cnt+=1
print(cnt)

Problème C

Après que le monstre avec la force physique la plus faible parmi les monstres donnés ait coupé la force physique des autres monstres, le monstre avec la force physique la plus faible parmi les monstres restants réduit la force physique des autres monstres. En répétant cette opération, il ne reste qu'un seul monstre à la fin, donc la solution requise pour la force physique de ce monstre. Quand je l'ai essayé avec un échantillon, etc., cela a fonctionné, et j'ai pensé qu'il serait impossible de le minimiser, alors j'ai écrit le code suivant. (Answer dit que la promesse maximale de force physique de tous les monstres est la solution que je fais sûrement. Même si vous considérez l'opération, vous pouvez voir qu'il s'agit du numéro d'engagement maximal.)

answerC.py


n=int(input())
a=list(map(int,input().split()))
while len(a)>1:
    l=len(a)
    a.sort()
    b=[a[0] if i==0 else a[i]%a[0] for i in range(l)]
    a=[b[i] for i in range(l) if b[i]!=0]
print(a[0])

Problème D

Tout d'abord, le premier code est un mauvais code typique (?). Je pensais à ** N ou moins ** au lieu de juste N **. En fait, dans le cas de ** N ou moins **, vous devriez réfléchir avec gourmandise, mais dans le cas de ** juste N **, vous devez penser à la combinaison **, donc DP ne peut pas être utilisé. C'est ça? J'ai eu l'idée. Si vous pouvez trouver un DP, ce n'est pas trop difficile. Si vous pensez à ** dp [i] comme le nombre maximum qui peut être représenté lorsque seulement i est utilisé ** (notez que a est trié par ordre décroissant par valeur numérique), alors a [i] [0] Le i-ème plus grand nombre, a [i] [1], est le nombre d'allumettes nécessaires pour représenter ce nombre, `dp [j + a [i] [1]]] = max (dp [j +] a [i] [1]], dp [j] * 10 + a [i] [0]) Mettez à jour pour trouver dp [n]. De plus, une fois qu'un certain ensemble de nombres est décidé, le nombre de correspondances est déterminé de manière unique ** Il est préférable de mettre les plus grands nombres dans l'ordre à partir du chiffre supérieur **, alors triez un par ordre décroissant et prenez le DP dans l'ordre du plus grand nombre. Vous pouvez y parvenir en faisant (par exemple 9 → 3 → 3 → 2 dans cet ordre, $ ((((0 \ fois 10 + 9) \ fois 10 + 3) \ fois 10 + 3) \ times 10 + 2) = 9332 $, et c'est certainement vrai. ** Je pense que c'est le premier DP du type qui donne des résultats différents dans l'ordre des éléments. **).

answerD_WA.py


n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
mi=a[0]
for i in range(1,m):
    if mi[1]>a[i][1] or (mi[1]==a[i][1] and a[i][0]>mi[0]):
        mi=a[i]
a=[a[i] for i in range(m) if a[i][0]>=mi[0]]
m=len(a)
b=sorted(a,key=lambda x:x[1])
c=sorted(a,reverse=True)#Enfin mi
d1=n//mi[1]#Nombre de chiffres
ans=[mi[0]]*d1
d2=n%mi[1]#Combien peut être utilisé plus tard
now=0#Qu'est-ce que tu essaies de changer en ans
for i in range(m-1):
    y=d2//(c[i][1]-mi[1])
    if y!=0:
        for j in range(now,now+y):
            ans[j]=c[i][0]
        now+=y
        d2-=(c[i][1]-mi[1])*y
    if d2==0:
        break
cnt=0
for i in range(d1):
    cnt=cnt*10+ans[i]
print(cnt)

answerD.py


n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
a.sort(reverse=True)
dp=[0]*(n+1)
for i in range(m):
    for j in range(n+1):
        if j==0 or dp[j]!=0:
            if j+a[i][1]<=n:
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
print(dp[n])

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