[PYTHON] Competitive professional devotion diary 11th-14th days (7 / 5-7 / 8)

Impressions

I missed one day, but I want to stay motivated and continue this month. During this devotion diary, I hope to stabilize the problems of light blue and blue and become a blue coder. I also have to study for graduation research, so I want to do my best. I'm groping because I don't know how much it is easy to read, but I hope I can update it once every three days.

11th day

ABC132-E Hopscotch Addict

Time taken

About 30 minutes

Consideration

** Since we want the shortest distance without weight, we will use BFS **. First of all, I thought about how to update the destination to reach when three consecutive kenkenpa as a new side, but if you think about the sides extending from each vertex in order, ** obviously it is not in time and there are many useless calculations **. I rejected it.

Here, assuming that you can reach the destination (movement of at most $ M $ times), if you repeat it 3 times, it will be a multiple of 3, so in the end ** movement of at most $ 3 \ times M $ times ** I noticed that Also, as mentioned above, if you can paraphrase ** to reach the destination at a distance that is a multiple of 3 **, consider the shortest distance in each of the three states where the distance to reach the destination is divided by three. I know it's good.

Therefore, considering the extended Dijkstra method in which each vertex has a state **, and considering the extended BFS ** in which each vertex has three states, an array that stores the shortest distance like a normal BFS ($ score [$ score [ i] [j]: = i $ Only when the shortest distance to the vertex is divided by 3 and the remainder is $ j $ (the shortest distance in the movement) and the array becomes inf. If it can be updated, it can be implemented with $ O (M + N) $.

import sys
sys.setrecursionlimit(10**6)
from collections import deque
n,m=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(m):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
s,t=map(int,input().split())
inf=100000000000
score=[[inf]*3 for i in range(n)]
now=deque()
now.append(s-1)
score[s-1][0]=0
def bfs(dep,l):
    global n,m,edges,s,t,score,inf,now
    f=False
    for i in range(l):
        ne=now.popleft()
        for j in edges[ne]:
            if score[j][dep%3]==inf:
                score[j][dep%3]=dep
                now.append(j)
    l_ne=len(now)
    if l_ne:bfs(dep+1,l_ne)
bfs(1,1)
if score[t-1][0]!=inf:
    print(score[t-1][0]//3)
else:
    print(-1)

12th day

I solved the ABC173-E that I couldn't pass during the contest. It is summarized in this article.

13th day

I was not good at using time. I'm sorry.

14th day

ABC135-D Digits Parade

Time taken

25 minutes

Consideration

Since I regretted it, I ACed the problem of low diff as soon as possible. I feel like I solved a similar problem before this, but I'm glad that I was able to AC in a reasonable amount of time. However, since I issued RE once, I regret it.

First of all, the biggest point is to notice DP. ** It is a character string and it is difficult to process the? Part **, **? Part is considered to increase the number of candidates ($ \ leftrightarrow $ transition method increases) **, ** With that character string Considering that the remainder of the numbers represented is determined by deciding the digits one by one **, I think it is not difficult to ship a DP that considers the state of each digit.

Here, consider the state of a given integer (character string representing) when looking up to ** $ i $ digits **, but here, considering the remainder, $ dp [i] [j]: = i It is good to know how many numbers are $ j $ when you look at the $ digit and divide by 13.

Then, regarding the transition of DP, the following two cases should be considered ($ p [i] $ is precalculated by dividing $ 10 ^ i $ by 13).

① When the $ i $ digit is $ k (0 \ leqq k \ leqq 9) $ The transition destination of $ dp [i] [j] $ is $ dp [i + 1] [(j + k * p [i])% 13] $.

② When the $ i $ digit is? All you have to do is do $ l $ in pattern ① from 0 to 9.

Also, I tried to find $ p [i] $ in the loop that performs DP, but since it is necessary to find $ 10 ^ {10 ^ 5-1} $ at the maximum, calculate only the remainder first. I tried to keep it.

Implement the above and get the following code.

mod=10**9+7
s=input()[::-1]
l=len(s)
dp=[[0]*13 for i in range(l+1)]
dp[0][0]=1
#Precalculation because the power is too large
p=[0]*l
p[0]=1
for i in range(l-1):
    p[i+1]=(p[i]*10)%13
for i in range(l):
    s_sub=s[i]
    if s_sub=="?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j+k*p[i])%13]+=dp[i][j]
                dp[i+1][(j+k*p[i])%13]%=mod
    else:
        k=int(s_sub)
        for j in range(13):
            dp[i+1][(j+k*p[i])%13]+=dp[i][j]
            dp[i+1][(j+k*p[i])%13]%=mod
print(dp[l][5])

ABC133-E Virus Tree 2

Time taken

It takes almost an hour but WA

Cause of mistake

I couldn't debug at all because I implemented it differently from my own consideration. ** I didn't have enough power to believe in my thoughts **, right? I'm not very good at debugging these patterns, but is it an experience ...? ??

Consideration

First, since it is a tree, it can be said that ** sides are N-1 sides, all vertices are connected, and there is no cycle **. Furthermore, the distance between two different vertices (the minimum number of sides required for tracing) is 2 or less (1 or 2).

Here, ** any tree can be considered as a rooted tree **, so I decided to consider a tree with vertex 1 as the root. Also, ** it is better to paint one color at a time so that the neighbors are painted differently **, so for the time being, I painted from the apex closest to the root. (If it was impossible, I intended to apply it from the leaves in reverse.)

Here, I decided to consider a tree with 8 vertices and 7 sides as shown in the figure below to check how to paint. Also, in the figure below, which vertex should not be different when painting from above is shown in red.

The language of how to paint the colors in the above figure is as follows.

First, there are $ K $ ways to paint the roots. Since the color of vertices other than the root is different from the color of vertices with a distance of 1 or 2, ** parent **, ** parent parent **, ** sibling (vertex with the same parent) * of that vertex Different from *. Here, since the parent of the parent does not exist at the peak of depth 1, ** How to paint the sibling color ** should be selected from $ K-1 $ street colors other than the parent $ \ _ {K-1} P \ _ {total number of siblings} $. In addition, since there is always one parent of the parent at the apex of depth 2, choose from $ K-2 $ colors other than the parent and the parent of the parent $ \ _ {K-2} P \ _ {siblings The total number of} $ will be.

Here, when I recorded how to paint the siblings' colors, I saved it in the array once, but ** I was recording the wrong value **. It would be very disappointing if I could make the test case accurately by myself as well as the sample.

from sys import setrecursionlimit
setrecursionlimit(10**6)
n,k=map(int,input().split())
paths=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)
inf=100000000000000
nums=[-inf]*n
nums[0]=k
from collections import deque
now=deque()
now.append(0)
def bfs(d):
    global n,k,paths,nums,now
    l=len(now)
    if d==1:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-1
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    else:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-2
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    if len(now):bfs(d+1)
bfs(1)
ans=1
for i in range(n):
    if nums[i]<=0:
        print(0)
        exit()
    ans*=nums[i]
    ans%=(10**9+7)
print(ans)