[PYTHON] yukicoder contest 264 Review


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


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.


for i in range(26):
    if s[i]!=t[i]:

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 **.


for x in range(1,z):
    if x**n+y**n==z**n:

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.


from itertools import dropwhile
a=list(dropwhile(lambda x:x==0,list(map(int,input().split()))[::-1]))[::-1]
if any(a[i]>i+1 for i in range(n)):
for i in range(n-1,-1,-1):
    if (c+a[i])%(i+1)!=0:

D problem

In the first place ** I made a mistake in calculating the probability **….

When calculating the probabilities, $ F and S $ are as follows.

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

In addition, $ F> S $ looks like this:

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

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:

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

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) $.


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

for _ in range(int(input())):

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.


from sys import setrecursionlimit
tree=[[] for i in range(n)]
for i in range(n-1):
dp=[[0,0] for i in range(n)]

def dfs(i):
    global n,a,b,tree,check,dp
    #When not erasing vertex i
    for j in tree[i]:
        if not check[j]:


F problem

I will not solve this time.

Recommended Posts

yukicoder contest 259 Review
yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 152 Review
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
yukicoder contest 266 Participation record
yukicoder contest 263 Participation record
yukicoder contest 243 Participation record
yukicoder contest 256 entry record
yukicoder contest 273 Participation record
Keyence Programming Contest 2020 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
yukicoder contest 252 Participation record
yukicoder contest 259 Participation record
AtCoder Beginner Contest 164 Review
yukicoder contest 249 Participation record
AtCoder Beginner Contest 169 Review
yukicoder contest 271 Participation record
AtCoder Grand Contest 048 Review
yukicoder contest 267 entry record
AtCoder Beginner Contest 181 Review
yukicoder contest 251 Participation record
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
yukicoder contest 242 Participation record
AtCoder Beginner Contest 180 Review
yukicoder contest 241 Participation record
yukicoder contest 277 Participation record
AtCoder Beginner Contest 177 Review
yukicoder contest 264 entry record
AtCoder Beginner Contest 168 Review
AtCoder Grand Contest 045 Review
NOMURA Programming Contest 2020 Review
AtCoder Grand Contest 044 Review
yukicoder contest 245 entry record
yukicoder contest 257 Participation record
yukicoder contest 250 entry record
yukicoder contest 254 Participation record
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
yukicoder contest 274 Participation record
AtCoder Beginner Contest 176 Review
yukicoder contest 247 Participation record
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
HHKB Programming Contest 2020 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review