[PYTHON] Yukicoder-Wettbewerb 264 Bewertung

Ergebnis

Impressionen

Ich war ungeduldig und konnte mich auch diesmal nicht für die Politik entscheiden. Es gibt viele Probleme, die gelöst werden können, wenn Sie ruhig bleiben, und ich bin der Meinung, dass Sie die Fähigkeit benötigen, Richtlinien zu organisieren **.

Problem A

Achten Sie einfach auf die Zeichen, die Sie ändern.

A.py

t="abcdefghijklmnopqrstuvwxyz"
s=input()
for i in range(26):
    if s[i]!=t[i]:
        print(t[i]+"to"+s[i])
        break

B-Problem

Ich denke, dass es auch einfach ist, eine Richtlinie wie Problem A zu erstellen. Aufgrund von Einschränkungen kann $ x $ (oder $ y $) nur 1 ~ $ z $ -1 annehmen, also führen Sie eine ** vollständige Suche ** durch.

B.py

n,z=map(int,input().split())
for x in range(1,z):
    y=int((z**n-x**n)**(1/n))
    if x**n+y**n==z**n:
        print("Yes")
        break
else:
    print("No")

C-Problem

Die Probleme A und B waren nicht schlecht, aber ich konnte die Richtlinie nicht beenden.

Betrachten Sie zunächst ** naive Simulation **. Zu diesem Zeitpunkt, wenn $ a [i]> i $ ist, kann mindestens $ a [i] $ nicht verschoben werden **, so dass ** jedes $ i $ als $ a [i] verwendet werden kann. \ leqq i $ ** muss gelten (✳︎1). Da diese Bedingung während der Simulation immer gelten muss, sollte die Simulation in der Reihenfolge des kleinsten $ i $ durchgeführt werden, in dem ** $ a [i] = i $ gilt (✳︎2).

Hier ist die naive Simulation $ O (N ^ 2) $, aber in der naiven Simulation wird +1 zu allem von 0 bis $ i $ -1 hinzugefügt, also das Element vor dem ** $ i $ -ten Element. Wenn Sie speichern, wie oft Sie +1 ** ausgeführt haben, können Sie mit $ O (N) $ effizient rechnen. Aus diesem Grund werden wir auch prüfen, ob es möglich ist, Steine in der Reihenfolge des größten $ i $ zu verschieben, dies unterscheidet sich jedoch ** von der Simulationsreihenfolge ** ($ \ weil $ (✳︎2)). Die Gesamtzahl der sich bewegenden Steine ist jedoch unabhängig von der Reihenfolge der Simulation gleich. ** Die Simulation kann nach Belieben durchgeführt werden, solange die Anzahl der Steine korrekt ist.

Wenn hier die Anzahl der Steine, die sich beim Betrachten des $ i $ -ten Quadrats bewegen, $ c $ beträgt, beträgt der Stein, der sich von diesem Quadrat bewegt, $ a [i] + c $ **. Es wird sein. Wenn zu diesem Zeitpunkt $ (a [i] + c) % i = 0 $ ist, können Sie diese Zelle verlassen. Wenn es verschoben werden kann, gilt $ c = c + \ frac {a [i] + c} {i} $. Denken Sie für jedes Quadrat darüber nach, und wenn es gilt, ist es Ja, andernfalls Nein.

(✳︎) 1… Wenn Sie die Problemstellung sorgfältig lesen, gilt diese Bedingung immer…. Es ist ein Spiegelbild.

C.py

from itertools import dropwhile
n=int(input())
a=list(dropwhile(lambda x:x==0,list(map(int,input().split()))[::-1]))[::-1]
n=len(a)
if any(a[i]>i+1 for i in range(n)):
    print("No")
    exit()
c=0
for i in range(n-1,-1,-1):
    if (c+a[i])%(i+1)!=0:
        print("No")
        break
    c+=(c+a[i])//(i+1)
else:
    print("Yes")

D Problem

Erstens ** habe ich einen Fehler bei der Berechnung der Wahrscheinlichkeit gemacht **….

Bei der Berechnung der Wahrscheinlichkeit sind $ F und S $ wie folgt.

\begin{align}
F&=\frac{M \times _NC_K}{_{NM}P_K}\\
S&=\frac{(N-K+1) \times M^K}{_{NM}P_K}
\end{align}

Außerdem sieht $ F> S $ folgendermaßen aus:

\begin{align}
&\frac{M \times _NC_K}{_{NM}P_K}>\frac{(N-K+1) \times M^K}{_{NM}P_K}\\
&\leftrightarrow M \times _NC_K>(N-K+1) \times M^K\\
&\leftrightarrow _NC_K>(N-K+1) \times M^{K-1}
\end{align}

Wenn die Berechnung so durchgeführt wird, wie sie ist, kostet sie ungefähr $ O (K) $ für jede Abfrage **, daher werden wir versuchen, sie durch Vorberechnung zu beschleunigen. Da es sich jedoch um eine Multiplikation handelt, handelt es sich um eine große Anzahl und einen Überlauf sowie einen großen Rechenaufwand Es braucht Zeit. Verwenden Sie also ** logarithmisch, um die Multiplikation auf eine überschaubare Addition zu korrigieren **. Das heißt, $ F> S $ sieht folgendermaßen aus:

\begin{align}
&N! \div (N-K)! \div K!>(N-K+1) \times M^{K-1}\\
&\leftrightarrow \sum_{i=1}^{N}{\log{i}}-\sum_{i=1}^{N-K}{\log{i}}-\sum_{i=1}^{K}{\log{i}}>\log{(N-K+1)}+(K-1)\log{M}
\end{align}

Hier sollte für den Teil $ \ log $ die kumulative Summe ($ a [i]: = \ sum_ {j = 1} ^ {i} {\ log {j}} $) im Voraus erhalten werden. Kann berechnet werden mit $ O (N_ {max}) $ ($ N_ {max} $ ist höchstens $ 10 ^ 5 $).

Aus dem oben Gesagten kann jede Abfrage mit $ O (1) $ berechnet werden, sodass der Gesamtbetrag der Berechnung $ O (N_ {max} + Q) $ beträgt.

D.py

from math import log2
from itertools import accumulate
x=[0]+[log2(i) for i in range(1,10**5+1)]
a=list(accumulate(x))

for _ in range(int(input())):
    n,m,k=map(int,input().split())
    ans=["Flush","Straight"]
    print(ans[a[n]-a[n-k]-a[k]>(a[n-k+1]-a[n-k])+(k-1)*(a[m]-a[m-1])])

E Problem

Wahrscheinlich das dritte Mal, dass ich das DP-Problem auf Kigami gelöst habe, aber ich konnte es sofort erkennen (ich habe andere Probleme während des Wettbewerbs gelöst ...).

Zunächst sind ** Informationen über die Anzahl der verbundenen Seiten ** beteiligt, sodass Sie sehen können, dass wahrscheinlich ** DFS oder BFS ** verwendet wird. Da außerdem jede Punktzahl oben festgelegt ist und ** nicht gierig entschieden werden kann ** und ** jede Spitze nur zwei Zustände hat, unabhängig davon, ob sie existiert **, ** DP im Baum Sie können es sich als ** vorstellen.

Und im Fall von DP in einem Baum von DFS ** kennen Sie an einem bestimmten Scheitelpunkt bereits die Informationen des Teilbaums, dessen Scheitelpunkt das Kind dieses Scheitelpunkts ist **, und ** verbinden den Scheitelpunkt, den Sie gerade betrachten, mit dem Kind. Es scheint, dass es implementiert werden kann, indem man auf die Seite ** achtet, also werden wir es hier durch DFS implementieren.

Der DP wird wie folgt eingestellt.

$ dp [i] [j]: = $ (maximale Punktzahl in Teilbäumen, die in $ i $ verwurzelt sind) (Wenn jedoch $ j = 0 $ ist, wird der Scheitelpunkt gelöscht, und wenn $ j = 1 $, wird der Scheitelpunkt nicht gelöscht.)

Betrachten Sie nun den DP-Übergang, bei dem der Scheitelpunkt, den Sie betrachten, $ i $ und der untergeordnete Scheitelpunkt $ j $ ist. Außerdem hat DFS bereits $ dp [j] $ berechnet.

(1) Übergang zu $ dp [i] [0] $

Das Hinzufügen von $ i $ erhöht nur $ a [i] $.

Wenn auf jedes $ j $ geachtet wird und $ j $ existiert, existieren beide $ i $, so dass $ b [i] + b [j] $ zunimmt.

Wenn der obige Übergang implementiert ist, ist er wie folgt. Wenn Sie nicht vergessen, das rekursive Limit zu erhöhen und es zu einer benachbarten Liste zu machen, können Sie es so implementieren, wie es ist.

E.py

from sys import setrecursionlimit
setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
tree=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
check=[False]*n
dp=[[0,0] for i in range(n)]

def dfs(i):
    global n,a,b,tree,check,dp
    #Wenn der Scheitelpunkt nicht gelöscht wird i
    dp[i]=[a[i],0]
    for j in tree[i]:
        if not check[j]:
            check[j]=True
            dfs(j)
            dp[i][0]+=max(dp[j][0],dp[j][1])
            dp[i][1]+=max(dp[j][0],dp[j][1]+b[i]+b[j])

check[0]=True
dfs(0)
print(max(dp[0]))

F Problem

Ich werde diesmal nicht lösen.