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

Benötigte Zeit

Impressionen

D Das Problem war eng ... Ich habe viele Fehler gemacht, weil ich für das C-Problem nicht viel von dieser Art von DP gemacht habe, also muss ich die DP richtig abdecken ... Ich schien in der Lage zu sein, das D-Problem mit einer lügengerechten Lösung zu lösen, aber es ist überhaupt nicht gut, also las ich die Antwort ... (Es ist enttäuschend, dass es nicht zahnig zu sein scheint, wenn es gelb wird. Schließlich hatte ich das Gefühl, dass dieses Problem durch eine Überprüfung gelöst werden könnte.)

Problem A

Wird es k überschreiten oder nicht überschreiten?

answerA.py

n=int(input())
k=int(input())
x=int(input())
y=int(input())
print(x*n if n<=k else x*k+y*(n-k))

B-Problem

Wie viele es gibt, können Sie durch Sortieren und Gruppieren herausfinden. Wenn es eine ungerade Zahl gibt, geben Sie die Nr.

answerB.py

def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2
w=list(input())
w.sort()
w=groupby(w)
for i in w:
    if i[1]%2==1:
        print("No")
        break
else:
    print("Yes")

C-Problem

Ich habe das Gefühl, dass das C-Problem diesmal etwas schwierig war. Der Durchschnitt sollte A sein, aber wenn es n Blätter gibt, ist die Summe schließlich n * A. Außerdem habe ich über DP ** nachgedacht, weil es schwierig ist, gierig an einen solchen Fall zu denken ** und ich eine Karte gut auswählen muss (ich bin der Meinung, dass die meisten DPs ein Muster haben, das sie innerhalb der Grenzen gut auswählen können). .. Obwohl es nur ein DP ist, bin ich ziemlich verwirrt, weil ich normalerweise an min und max denke. Notieren Sie zunächst ** dp [j] [k], wie viele Fälle die ganze Zahl j durch k Karten dargestellt werden kann ** (dp [0] [0] lässt sich später leicht berechnen). Lass es bei 1.). Wenn Sie die Ganzzahl $ x_i $ in dp [j] [k] betrachten und dp [j] [k] = 0 ist, kann die Ganzzahl j zu diesem Zeitpunkt nicht durch k Karten dargestellt werden. Aktualisieren Sie sie daher. Wenn jedoch dp [j] [k] $ \ ne0 $ ist, aktualisieren Sie als `dp_sub [j + x [i]] [k + 1] = dp [j] [k]` ( Da es jeweils eine Karte gibt, müssen Sie dp_sub vorbereiten.) Wenn Sie dann (+) reflektieren, was Sie in dp_sub in dp geschrieben haben, ist das Update abgeschlossen, und Sie können sich dies als i: 1 → n vorstellen. Schließlich erhält man die Antwort durch Addition der Elemente (dp [a * (i + 1)] [i + 1] `), wobei der Durchschnitt der ganzen Zahlen von dp genau a ist.

answerC.py

n,a=map(int,input().split())
x=list(map(int,input().split()))
x.sort(reverse=True)
sx=sum(x)
dp=[[0]*(n+1) for i in range(sx+1)]
dp[0][0]=1
for i in range(n):
    dp_sub=[[0]*(n+1) for j in range(sx+1)]
    for j in range(sx+1):
        for k in range(n+1):
            if dp[j][k]!=0:
                dp_sub[j+x[i]][k+1]=dp[j][k]
    for j in range(sx+1):
        for k in range(n+1):
            dp[j][k]+=dp_sub[j][k]
cnt=0

for i in range(min(sx//a,n)):
    cnt+=dp[a*(i+1)][i+1]
print(cnt)

D Problem

Hmmm, ist die Antwort nicht zu genial, egal wie oft Sie sie ansehen? Im Folgenden werde ich nach dieser Antwort in meinen eigenen Worten organisieren.

Erstens, wenn Sie an die Zeit von ** n \ <s ** denken, wird f (b, n) immer kleiner oder gleich b sein (ich habe es nicht bewiesen, aber ich denke nicht, dass es so schwierig ist). Es gibt kein b, das f (b, n) = s erfüllt (Ausgänge -1). Als nächstes betrachte man die Zeit von ** n = s **, b \ <= n ist f (b, n) \ <s und b > = n + 1 ist (b, n) = s, also b Es ist leicht zu erkennen, dass = n + 1 das kleinste ist. Im Folgenden werden wir mit der Diskussion als ** n > s ** fortfahren.

Erstens ist es $ n \ leqq 10 ^ {11} $, aber da es nicht monoton ist und keine Dichotomie verwendet werden kann, kann es möglich sein, es mit ** $ O (\ sqrt {n}) $ zu übergeben, was der nächste kleine Rechenaufwand zu sein scheint. Ich vermute, es ist nicht ** (Ich habe dies bemerkt, es ist ein Bild **, das sich mit dem Berechnungsbetrag von ** $ O (\ sqrt {n}) $ auf den zugänglichen Bereich einschränkt). Zur Zeit b: 2 → $ \ sqrt {n} $, um das kleinste b zu finden, für das $ f (b, n) = s $ ist, und falls nicht gefunden, $ \ sqrt {n} <b \ leqq n $ für das kleinste Angenommen, Sie suchen nach b. Dann $ \ sqrt {n} <b \ leqq n $. Wenn Sie also feststellen, dass ** n immer 2-stellig ist **, wenn Sie in b-ary denken, $ 1 \ leqq p <b $, $ 0 \ leqq q Es kann ausgedrückt werden als <b $ durch $ n = pb + q $… (1). Weiterhin kann $ p + q = s $… (2) aus dem Subjekt gesagt werden.

Außerdem gilt ab (1) $ n = pb + q> pb> p ^ 2 $, sodass Sie $ 1 \ leqq p <\ sqrt {n} $ sagen können ** Motivation, den Bereich von p und q einzugrenzen **.). Daher wird der Kandidat für p durch $ O (\ sqrt {n}) $ gefunden, und b wird aus den Gleichungen (1) und (2) eindeutig als $ b = (ns) / p + 1 $ bestimmt. Die Lösung kann gefunden werden, indem nach dem kleinsten b gesucht wird, so dass $ f (b, n) = s $.

Das Obige ist implementiert und wird wie folgt. (Ich brauchte anderthalb Stunden zum Debuggen und vergaß das = in dem Teil des Codes, der "hier" sagt. Ich bin im Begriff zu sterben.)

answerD.py

import math
n=int(input())
s=int(input())

def f(b,n):
    m=math.floor(n/b)
    if n>=b:#Hier
        return f(b,m) + n%b
    else:
        return n

if n<s:
    print(-1)
elif n==s:
    print(n+1)
else:
    for i in range(2,int(math.sqrt(n))+1):
        if f(i,n)==s:
            print(i)
            break
    else:
        for p in range(int(math.sqrt(n)),0,-1):
            if (n-s)%p==0:
                b=(n-s)//p+1
                if f(b,n)==s:
                    print(b)
                    break
        else:
            print(-1)