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

Temps requis

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])