[PYTHON] AtCoder Beginner Contest 180 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Es war eine gute Note. Dieses F war schwierig und ich hatte nicht das Gefühl, es überhaupt lösen zu können. Ich habe es verstanden, indem ich mir die Antwort angesehen habe, aber es scheint, dass sie nicht angewendet werden kann, also werde ich diesmal nicht auflösen. Mir wurde klar, dass das E-Problem typisch war. Es war ein typisches Muster, das ich noch nie zuvor gelöst hatte, daher würde ich es gerne oft überprüfen.

Problem A

Ich dachte, dass das Problem nicht festgestellt wurde, wenn $ n <a $, aber $ n \ geqq a $ aufgrund der Einschränkung gilt.

A.py

n,a,b=map(int,input().split())
print(n-a+b)

B-Problem

Implementieren Sie es einfach gemäß der Problemstellung. Tatsächlich ist es kein Problem, wenn Sie die Eingabe so wie sie ist in einen absoluten Wert konvertieren.

B.py

n=input()
x=list(map(lambda y:abs(int(y)),input().split()))
print(sum(x),sum([i*i for i in x])**0.5,max(x))

C-Problem

Ich habe falsch verstanden, dass es in Ordnung war, zusätzliche Windbeutel zu haben, als ich es verteilte, und habe falsch verstanden, dass es ein Problem war, Kandidaten für den Wert von $ [\ frac {n} {k}] $ zu finden.

Alles, was Sie tun müssen, ist, die Brüche so aufzulisten, wie sie verteilt werden, damit es keinen Überschuss gibt.

C.py

def m():
    n=int(input())
    d=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            d+=[i]
            if i!=n//i:d+=[n//i]
    d.sort()
    return d
for i in m():print(i)

D Problem

Es geht nur darum, die Fälle ruhig zu klassifizieren, aber ich habe 2WA ausgestellt ... Infolgedessen war es eine blaue Leistung, wenn 1WA ausreichte, also bin ich enttäuscht.

Wählen Sie zwischen Multiplikation von A und Addition von B. Ersteres und Letzteres treffen die beste Wahl, aber ** wenn Ersteres nicht mehr optimal ist, ist Letzteres danach immer das Beste **. Sie können dies auch sehen, indem Sie den Änderungsbetrag zwischen $ \ times A $ und $ + B $ vergleichen.

Betrachten Sie daher den Fall, in dem es am besten ist, $ x $ mit A zu multiplizieren (wenn der Wert von $ x $ multipliziert mit A kleiner ist als der Wert von $ \ leftrightarrow $$ x $ plus B). Zu diesem Zeitpunkt ist es natürlich, $ x \ times A \ leqq x + B $ im bedingten Vergleichsausdruck zu verwenden, aber es ist auch erforderlich, die Bedingung ** festzulegen, um ** $ x \ <y $ zu erfüllen. Wenn Sie es sorgfältig in der Schleife implementieren, erfordert die Berechnung des Hinzufügens von $ B $ nach dem Verlassen der Schleife nur $ ans + [\ frac {y-x-1} {b}] $.

D.py

x,y,a,b=map(int,input().split())
ans=0
while True:
    if x*a<=x+b:
        if x*a>=y:
            print(ans)
            exit()
        else:
            ans+=1
            x*=a
    else:
        #Von hier+
        #x*a>x+b
        #x<y
        break
print(ans+(y-x-1)//b)

E Problem

Es scheint, dass es ein typisches Problem war, aber wenn ich es mir nach der Lösung anschaue, habe ich das Gefühl, dass es auch der Fall ist.

Der Prozess der Prüfung des Wettbewerbs wird unten beschrieben. Außerdem müssen die dreidimensionalen Koordinaten des Subjekts auf der $ x $ -Achse, der $ y $ -Achse und der $ z $ -Achse gestreckt werden.

Erstens ist das Maximum $ n = 17 $, also ist ** $ n! $ Nicht rechtzeitig **. Ich konnte nicht versuchen, es anzuwenden, da das häufigste Problem mit $ 2 ^ n $ eine halb vollständige Aufzählung ist. Als nächstes dachte ich darüber nach, ** die Kostenformel zu betrachten und zu prüfen, ob sie gut entschieden werden kann **, aber wenn ich die beiden Eckpunkte verbinde, scheint es besser, von der größeren $ z $ -Koordinate zur kleineren zu verbinden. Ich weiß nur. Wenn Sie sich die Einschränkung ansehen, werden Sie feststellen, dass sie ** übergeben wird, wenn es sich um BitDP handelt, weil es ** $ 2 ^ {17} $ ist. In Anbetracht der DP, die die Anzahl der eingetroffenen Städte verwaltet, ist dies wie folgt.

$ dp [i] [j]: = $ (Summe der Mindestkosten, wenn die in der Teilmenge $ i $ enthaltenen Städte erreicht wurden und sich in der Stadt $ j $ befinden)

** Wenn Sie die Menge der Städte, die Sie erreicht haben, in Bits darstellen möchten, können Sie daran denken, solange Sie sich daran erinnern, dass es sich um BitDP handelt **. Diese Ausgabe ist auch eine Variante des berühmten TSP (Circular Salesman Problem).

Hier sollte die Reihenfolge der DP-Übergänge wie folgt in der Reihenfolge kleinerer Zustände $ i $ (Ganzzahl) ** (✳︎) sein. Die Initialisierung erfolgt nur für $ dp [1] [0] = 1 $. (Betrachten Sie den Übergang zur Stadt $ k $, wenn Sie sich für ein bestimmtes $ i $ in der Stadt $ j $ befinden. Sie müssen nicht denken, wenn $ j = k $ ist. Außerdem ist $ dist [j] [k] $ $ Die Kosten für den Wechsel von j $ zu $ k $.)

dp[i|(1\<\

Aus dem oben Gesagten ist $ dp [1 \ <\ <n-1] [0] $ die Antwort, da ** schließlich zu Stadt 1 zurückkehrt.

(✳︎)… Ich werde beweisen, dass Sie es in aufsteigender Reihenfolge tun können. Mit anderen Worten wird hier gezeigt, dass jede Art von Bewegung ausgedrückt werden kann.

Beim Übergang vom Zustand von $ i $ zu $ j $ → $ k $ wird der Zustand zu $ i $ → $ i | (1 \ <\ <k) $. Mit anderen Worten, wenn Sie ** bitweise oder nehmen, nimmt der Zustand (die ganzzahlige Darstellung) nicht ab **. Wenn Sie also einen Übergang (Aktualisierung) ** in aufsteigender Reihenfolge des ** Zustands (Indikator darstellt) durchführen, können Sie alle Bewegungsmethoden ausdrücken. Wenn der Übergang als gerichtete Seite mit jedem Zustand $ i $ als Scheitelpunkt betrachtet wird, kann er auch von dem kleineren ** $ i $ aktualisiert werden, wenn ** topologisch sortiert, und dies gilt für BitDP. Ich denke, es kann interpretiert werden. Darüber hinaus können Sie verstehen, dass die Ganzzahl, die den Status im Übergang darstellt, nicht abnimmt, da $ j $ kleiner als ** $ i $ $ i $ ** nicht enthält.

[Aktualisiert am 18. Oktober 2020]

In der obigen Diskussion wird implizit verwendet, dass es kürzer ist, nicht durch eine andere Stadt zu fahren, wenn von einer Stadt in eine andere gewechselt wird. Dies liegt jedoch daran, dass die Ungleichung des Dreiecks eine Kostenformel ist. Es kann aus der Tatsache gezeigt werden, dass es gilt **. Wenn es kürzer ist, durch andere Städte zu fahren, können Sie ** zuerst die Kosten zwischen allen Städten mit Worshall Floyd ermitteln und dann ** das gleiche BitDP durchführen.

E.py

n=int(input())
tos=[list(map(int,input().split())) for i in range(n)]
#Kosten von 1 bis j
def co(i,j):
    return abs(i[0]-j[0])+abs(i[1]-j[1])+max(0,j[2]-i[2])
inf=10**12
dp=[[inf for j in range(n)] for i in range(1<<n)]
dp[1][0]=0
for i in range(1,1<<n):
    for j in range(n):
        #Kehre niemals zu mir zurück
        for k in range(n):
            if j==k:continue
            dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+co(tos[j],tos[k]))
ans=inf
for i in range(n):
    ans=min(ans,dp[(1<<n)-1][i]+co(tos[i],tos[0]))
print(ans)

F Problem

Ich werde diesmal nicht lösen.