[PYTHON] AtCoder Beginner Contest 118 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

D Problem falsch gelesen ... Das D-Problem war interessant mit einer neuen Form von DP, ich mag es ziemlich.

Problem A

Bestimmen Sie, ob b% a 0 ist

answerA.py

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

B-Problem

Ich habe zu viel Zeit damit verbracht, es umzusetzen ... Sie können beurteilen, ob jeder die m Typen mag.

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)

C-Problem

Nachdem das Monster mit der niedrigsten physischen Stärke unter den gegebenen Monstern die physische Stärke der anderen Monster verringert hat, verringert das Monster mit der niedrigsten physischen Stärke unter den verbleibenden Monstern die physische Stärke der anderen Monster. Wenn Sie diesen Vorgang wiederholen, bleibt am Ende nur ein Monster übrig, sodass die Lösung für die physische Stärke dieses Monsters erforderlich ist. Als ich es mit einem Beispiel usw. versuchte, funktionierte es und ich dachte, dass es unmöglich sein würde, es zu minimieren, also schrieb ich den folgenden Code. (Antwort sagt, dass das maximale Versprechen der körperlichen Stärke aller Monster die Lösung ist, die ich mit Sicherheit mache. Selbst wenn Sie die Operation in Betracht ziehen, können Sie sehen, dass es sich um die maximale Verpflichtungszahl handelt.)

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

D Problem

Erstens ist der erste Code ein typischer (?) Falscher Code. Ich dachte an ** N oder weniger ** anstatt nur an N **. Eigentlich sollten Sie im Fall von ** N oder weniger ** gierig denken, aber im Fall von ** nur N ** müssen Sie über die Kombination ** nachdenken, damit DP nicht verwendet werden kann. Ist es? Ich kam auf die Idee. Wenn Sie einen DP finden können, ist das nicht allzu schwierig. Unter Berücksichtigung von ** dp [i] ist die maximale Anzahl, die dargestellt werden kann, wenn genau i ** verwendet wird (beachten Sie, dass a in absteigender Reihenfolge nach numerischem Wert sortiert ist), a [i] [0] Die i-te größte Zahl, a [i] [1], ist die Anzahl der Streichhölzer, die erforderlich sind, um diese Zahl darzustellen. `Dp [j + a [i] [1]]] = max (dp [j +] a [i] [1]], dp [j] * 10 + a [i] [0]) Aktualisiere `, um dp [n] zu finden. Sobald ein bestimmter Satz von Zahlen festgelegt ist, wird die Anzahl der Übereinstimmungen eindeutig bestimmt. ** Es ist am besten, die größten Zahlen in der Reihenfolge von der obersten Ziffer einzugeben **. Sortieren Sie also eine in absteigender Reihenfolge und nehmen Sie den DP in der Reihenfolge von der größten Zahl. Sie können dies erreichen, indem Sie (z. B. 9 → 3 → 3 → 2 in dieser Reihenfolge $ ((((0 \ mal 10 + 9) \ mal 10 + 3) \ mal 10 + 3)) ausführen. \ times 10 + 2) = 9332 $, und es gilt mit Sicherheit. ** Ich glaube, dies ist der erste DP des Typs, der unterschiedliche Ergebnisse in der Reihenfolge der Elemente liefert. **).

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)#Endlich mi
d1=n//mi[1]#Anzahl an Ziffern
ans=[mi[0]]*d1
d2=n%mi[1]#Wie viel kann später verwendet werden
now=0#Was versuchst du in ans zu ändern?
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])