concours yukicoder 264 avis

résultat

スクリーンショット 2020-09-05 11.12.16.png

Impressions

J'étais impatient et je ne pouvais pas non plus décider de la politique cette fois. Il existe de nombreux problèmes qui peuvent être résolus si vous restez calme, et je pense que vous avez besoin de la capacité d'organiser des politiques **.

Problème A

Faites juste attention aux personnages qui changent.

A.py


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

Problème B

Je pense qu'il est également facile d'élaborer une politique comme le problème A. En raison de contraintes, $ x $ (ou $ y $) ne peut prendre que 1 ~ $ z $ -1, alors faites une ** recherche complète **.

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

Problème C

Les problèmes A et B n'étaient pas graves, mais je n'ai pas pu terminer la politique.

Tout d'abord, considérons la ** simulation naïve **. À ce stade, lorsque $ a [i]> i $, au moins ce $ a [i] $ ne peut pas être déplacé **, donc ** tout $ i $ peut être utilisé comme $ a [i]. \ leqq i $ ** doit contenir (✳︎1). De plus, puisque cette condition doit toujours être vérifiée pendant la simulation, la simulation doit être effectuée dans l'ordre à partir du plus petit $ i $ dans lequel ** $ a [i] = i $ tient (✳︎2).

Ici, la simulation naïve est $ O (N ^ 2) $, mais dans la simulation naïve, +1 est ajouté à tout de 0 à $ i $ -1, donc l'élément avant l'élément ** $ i $ ème. Si vous enregistrez le nombre de fois que vous avez fait +1 **, vous pouvez calculer efficacement avec $ O (N) $. Aussi, pour cette raison, nous examinerons s'il est possible de déplacer les pierres dans l'ordre du plus grand $ i , mais ceci est ** différent de l'ordre de simulation ** ( \ parce que $ (✳︎2)). Cependant, le nombre total de pierres en mouvement est le même quel que soit l'ordre de la simulation, donc ** la simulation peut être effectuée à votre convenance tant que le nombre de pierres est correct.

Ici, si le nombre de pierres se déplaçant en regardant le $ i $ th carré est $ c $, alors la pierre se déplaçant de ce carré est $ a [i] + c $ **. Ce sera. À ce stade, si $ (a [i] + c) % i = 0 $, vous pouvez quitter cette cellule. De plus, quand il peut être déplacé, $ c = c + \ frac {a [i] + c} {i} $ tient. Pensez-y pour n'importe quel carré, et s'il tient, ce sera Oui, sinon ce sera Non.

(✳︎) 1… Si vous lisez attentivement l'énoncé du problème, cette condition est toujours vraie…. C'est une réflexion.

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

Problème D

En premier lieu ** j'ai fait une erreur dans le calcul de la probabilité **….

Lors du calcul de la probabilité, $ F et S $ sont les suivants.

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

De plus, $ F> S $ ressemble à ceci:

\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}

Si le calcul est effectué tel quel, il coûtera environ $ O (K) $ pour chaque requête **, nous allons donc essayer d'accélérer par pré-calcul, mais comme il s'agit d'une multiplication telle quelle, ce sera un nombre énorme et un débordement et une grande quantité de calcul Ça prend du temps. Donc, ** utilisez logarithmique pour corriger la multiplication en une addition plus gérable **. Autrement dit, $ F> S $ ressemble à ceci:

\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}

Ici, pour la partie $ \ log , la somme cumulée ( a [i]: = \ sum_ {j = 1} ^ {i} {\ log {j}} $) doit être obtenue à l'avance. Peut être calculé par $ O (N_ {max}) $ ($ N_ {max} $ est au plus 10 $ ^ 5 $).

D'après ce qui précède, chaque requête peut être calculée par $ O (1) $, donc le montant total du calcul est $ O (N_ {max} + Q) $.

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 problème

Probablement la troisième fois que j'ai résolu le problème DP sur Kigami, mais j'ai pu le repérer immédiatement (je résolvais d'autres problèmes pendant le concours ...).

Tout d'abord, ** des informations sur le nombre de côtés connectés sont impliquées **, vous pouvez donc voir qu'il est susceptible d'utiliser ** DFS ou BFS **. De plus, puisque chaque score est fixé sur le dessus et ** ne peut pas être décidé avec gourmandise ** et ** chaque sommet n'a que deux états, qu'il existe ou non **, ** DP sur l'arbre. Vous pouvez le considérer comme **.

Et dans le cas de DP sur un arbre par DFS, ** lorsque vous êtes à un certain sommet, vous connaissez déjà les informations du sous-arbre dont le sommet est l'enfant de ce sommet **, et ** connectez le sommet que vous regardez et l'enfant Il semble qu'il puisse être implémenté en faisant attention au côté **, donc ici nous allons l'implémenter par DFS.

Le DP est réglé comme suit.

$ dp [i] [j]: = $ (score maximum dans les sous-arbres enracinés dans $ i $) (Cependant, lorsque $ j = 0 $, le sommet est effacé, et lorsque $ j = 1 $, le sommet n'est pas effacé.)

Considérons maintenant la transition DP, où le sommet que vous regardez est $ i $ et le sommet enfant est $ j $. De plus, DFS a déjà calculé $ dp [j] $.

(1) Transition vers $ dp [i] [0] $

Ajouter $ i $ augmentera seulement $ a [i] $.

dp[i][0]=a[i]+\sum_j{max(dp[j][0],dp[j][1])}

En faisant attention à chaque $ j $, si $ j $ existe, les deux $ i $ existent, donc $ b [i] + b [j] $ augmente.

dp[i][1]=\sum_j{max(dp[j][0],dp[j][1]+b[i]+b[j])}
dp[i]=[a[i],0]

Si la transition ci-dessus est mise en œuvre, ce sera comme suit. Si vous n'oubliez pas de ** augmenter la limite récursive ** et d'en faire une liste adjacente, vous pouvez l'implémenter telle quelle.

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
    #Lorsque vous n'effacez pas le sommet 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]))

Problème F

Je ne résoudrai pas cette fois.

Recommended Posts

concours yukicoder 259 avis
concours yukicoder 264 avis
concours yukicoder 261 avis
concours yukicoder 267 avis
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
Critique du concours AtCoder Beginner Contest 152
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
concours yukicoder 266 Record de participation
yukicoder contest 263 Record de participation
concours yukicoder 243 Record de participation
record de 256 entrées
yukicoder contest 273 Record de participation
Examen du concours de programmation Keyence 2020
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
concours yukicoder 252 Record de participation
concours yukicoder 259 Record de participation
Critique du concours AtCoder
concours yukicoder 249 Record de participation
AtCoder Débutant Contest 169 Évaluation
concours yukicoder 271 Record de participation
AtCoder Grand Contest 048 Critique
record de participation au concours 267 de yukicoder
Critique du concours AtCoder Débutant 181
Concours yukicoder 251 Record de participation
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
yukicoder contest 242 Record de participation
Critique du concours AtCoder Débutant 180
concours yukicoder 241 Record de participation
Critique du concours AtCoder pour débutant 177
record du concours 264 de yukicoder
AtCoder Débutant Contest 168 Critique
AtCoder Grand Contest 045 Critique
Revue du concours de programmation NOMURA 2020
AtCoder Grand Contest 044 Critique
yukicoder contest 245 record d'inscription
yukicoder contest 257 Record de participation
record de participation au concours yukicoder 250
Concours yukicoder 254 Record de participation
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
yukicoder contest 246 Record de participation
concours yukicoder 275 Record de participation
Concours yukicoder 274 Record de participation
Critique du concours AtCoder
concours yukicoder 247 Record de participation
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Examen du concours de programmation HHKB 2020
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique