[PYTHON] 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 , but this is ** different from the simulation order ** ( \ because $ (✳︎2)). However, the total number of moving stones is the same regardless of the order of the simulation, so the simulation can be done at your convenience as long as the number of stones is correct.

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.