yukicoder contest 264 Review
result
Impressions
I was impatient and couldn't decide the policy this time as well. There are many problems that can be solved if you keep calm, and I feel that you need the ability to organize policies **.
Problem A
Just pay attention to the characters you change.
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
I think this is also easy to make a policy like problem A. Due to constraints, $ x $ (or $ y $) can only take 1 ~ $ z $ -1, so ** search all **.
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
The problems A and B weren't bad, but I couldn't finish the policy.
First, consider ** naive simulation **. At this time, when $ a [i]> i $, at least that $ a [i] $ cannot be moved **, so ** any $ i $ can be used as $ a [i]. \ leqq i $ ** must hold (✳︎1). Also, since this condition must always hold during the simulation, the simulation should be performed in order from the smallest $ i $ in which ** $ a [i] = i $ holds (✳︎2).
Here, the naive simulation is $ O (N ^ 2) $, but in the naive simulation, +1 is added to everything from 0 to $ i $ -1, so the element before the ** $ i $ th element. If you save how many times you have done +1 **, you can calculate efficiently with $ O (N) $. Also, for this reason, we will consider whether it is possible to move stones in order from the largest $ i
Here, assuming that the number of stones moving when looking at the $ i $ th square is $ c $, the stone moving from that square is $ a [i] + c $ **. It becomes. At this time, if $ (a [i] + c) % i = 0 $, you can move from this cell. Also, when it can be moved, $ c = c + \ frac {a [i] + c} {i} $ holds. Think about this for any square, and if it holds, it will be Yes, otherwise it will be No.
(✳︎) 1… If you read the question sentence carefully, this condition always holds true…. It is a reflection.
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
In the first place ** I made a mistake in calculating the probability **….
When calculating the probabilities, $ F and S $ are as follows.
\begin{align}
F&=\frac{M \times _NC_K}{_{NM}P_K}\\
S&=\frac{(N-K+1) \times M^K}{_{NM}P_K}
\end{align}
In addition, $ F> S $ looks like this:
\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}
If the calculation is performed as it is, it will cost about $ O (K) $ for each query **, so we will try to speed up by pre-calculation, but since it is a multiplication as it is, it will be a huge number and overflow and a large amount of calculation It takes time. So, ** use logarithms to correct the multiplication to the easier addition **. That is, $ F> S $ looks like this:
\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}
Here, for the $ \ log $ part, the cumulative sum ($ a [i]: = \ sum_ {j = 1} ^ {i} {\ log {j}} $) should be obtained in advance. Can be calculated by $ O (N_ {max}) $ ($ N_ {max} $ is at most $ 10 ^ 5 $).
From the above, each query can be calculated by $ O (1) $, so the total amount of calculation is $ 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 problem
Probably the third time I solved the DP problem on Kigami, but I was able to spot it immediately (I was solving other problems during the contest ...).
First of all, ** information on the number of connected sides is involved **, so you can see that ** DFS or BFS is likely to be used **. Furthermore, since each vertex has a fixed score ** and ** cannot be greedily determined ** and ** each vertex has only two states, whether or not it exists **, ** DP on the tree. You can think of it as **.
And in the case of DP on a tree by DFS, ** when you are at a certain vertex, you already know the information of the subtree whose vertex is the child of that vertex **, and ** connect the vertex you are looking at now and the child. It seems that it can be implemented by paying attention to the side **, so here we will implement it by DFS.
The DP is set as follows.
$ dp [i] [j]: = $ (maximum score in subtree rooted in $ i $) (However, when $ j = 0 $, the vertex is erased, and when $ j = 1 $, the vertex is not erased.)
Now consider the DP transition, where the vertex you are looking at is $ i $ and the child vertex is $ j $. Also, DFS has already calculated $ dp [j] $.
(1) Transition to $ dp [i] [0] $
Adding $ i $ will only increase $ a [i] $.
When paying attention to each $ j $, if $ j $ exists, both $ i $ exist, so $ b [i] + b [j] $ increases.
If the above transition is implemented, it will be as follows. If you don't forget to ** raise the recursion limit ** and make it an adjacency list, you can implement it as it is.
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
#When not erasing vertex 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
I will not solve this time.
Recommended Posts