[PYTHON] AtCoder Beginner Contest 176 Review

This time's results

Impressions of this time

This time I endured it at the last minute ... The D problem didn't work and I got a bug in the C ++ implementation and it was too terrible. After all, ** mentality when impatient ** is the biggest issue. Also, I am reflecting on the D problem because I was doing ** non-essential speedup ** without considering it. I think I'll do my best to improve the accuracy of my consideration.

Problem A

You can burn $ x $ at a time, so you only have to burn $ ceil (\ frac {n} {x}) $ as many times as you like. Also, since it takes $ t $ to bake, $ ceil (\ frac {n} {x}) \ times t $ is output.

A.py

n,x,t=map(int,input().split())
y=-((-n)//x)
print(y*t)

B problem

You can think of the sum by converting each character into a number. Therefore, convert character by character with ʻint`.

B.py

n=input()
ans=0
for i in n:
    ans+=int(i)
print("Yes" if ans%9==0 else "No")

C problem

You can decide whether you need a stepping stone and the height of the stepping stone from the front. In other words, when $ a \ _ {i-1}> a \ _i $, the height of the stepping stone should be viewed as $ a \ _ {i-1} -a \ _i $ in order.

C.py

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,n):
    if a[i]<a[i-1]:
        ans+=(a[i-1]-a[i])
        a[i]=a[i-1]
print(ans)

D problem

First of all, it is a grid search problem, and since it is the minimum number of warp magics, it turns out that it seems good to use normal BFS or DFS.

However, if implemented normally, it will take time to search for the $ 5 \ times 5 $ cell of move B **, so we will improve efficiency. I thought that my implementation was bad and tried to increase the efficiency by a constant factor, but I clearly understand that the ** bottleneck here should be eliminated **.

It should be noted here that movement A does not use the number of warp magics, so movement A is optimal if it can be traced only by movement A **. Therefore, consider a BFS or DFS such as ** preferentially select and search move A **. Since it is difficult for DFS to change its search order arbitrarily, we will consider using BFS. In BFS, queue is used to ** insert after ** and search from front to **. However, in this case ** the move has no priority ** and it just follows the inserted ones in order. Therefore, this priority can be achieved by using a deque in BFS here, inserting it in front when doing move A, and inserting it in the back when doing move B. Also, a BFS ** that is inserted before if it is connected at the edge of ** cost 0 and inserted at the back if it is connected at the edge of cost 1 is called ** 01-BFS **.

Also, since both movements A and B are cost-consuming movements **, it is considered to be a fairly natural solution to solve by the ** Dijkstra method **. In other words, if we consider movement A as the side with cost 0 and movement B as the side with cost 1, we can reduce it to the problem of considering movement at the lowest cost. Therefore, when combined with the fact that the ** cost is non-negative **, it can be calculated as $ O (HW \ log {HW}) $ by the Dijkstra method ** with the grid as the vertex. (If you don't know 01-BFS, this is a natural idea, but I didn't come up with an idea because I haven't solved the shortest path problem recently ...)

(✳︎) The following BFS did not understand the policy after the contest, but was rewritten afterwards. ** In the case of searching on the grid, it is easy to implement and understand ** by writing the next grid to be followed with a for statement.

D.py

#Edge weight(Amount of change)If is 0, 01DFS is a special one
#If 0, you can BFS there
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
#Bfs on the grid is a for statement
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        for k,l in [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]:
            if 0<=k<h and 0<=l<w:
                if dp[k][l]!=-1:
                    if dp[k][l]>dp[i][j]:
                        dp[k][l]=dp[i][j]
                        now.appendleft([k,l])
        for k in range(i-2,i+3):
            for l in range(j-2,j+3):
                if 0<=k<h and 0<=l<w:
                    if dp[k][l]!=-1:
                        if dp[k][l]>dp[i][j]+1:
                            dp[k][l]=dp[i][j]+1
                            now.append([k,l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

E problem

Thanks to this problem, I was able to withstand the water performance. The inability to consider the D problem was unusual, but I think it was a considerable harvest to endure here.

First of all, if you think about it normally, it is best to select the row ($ MAXR ) and column ( MAXC $) that have the largest number of blast targets **, and the answer is $ MAXR + MAXC $. However, if there is a blast target on that ** intersecting grid **, the answer is $ MAXR + MAXC-1 $.

At this time, if you select a row or column that does not have the maximum number of blast targets, the number of blast targets included in that row and column will be $ MAXR + MAXC-1 $ or less, so ** the row with the maximum number of blast targets And you should choose a column **.

Here, there may be ** multiple rows and columns with the largest number of blast targets **, and the array containing each is assumed to be xr, xc. At this time, there are only len (xr) × len (xc) combinations of these rows and columns. Look for at least one row / column combination that is not at the intersection of the blast targets. Also, len (xr) × len (xc) has a maximum of $ (3 \ times 10 ^ 6) $, so it is ** difficult to try all combinations **.

Therefore, instead of trying every row and column combination, ** conversely look for each blast target in that combination . In other words, by converting xr and xc to a set and seeing if the index of each blast target is included in this set, it is possible to find out how many blast targets are in this combination. You can (check). ** If check is smaller thanlen (xr) x len (xc), there is at least one way to select rows and columns so that there is no blast target at the intersection, so $ MAXR If + MAXC $ is the solution and ** check is equal tolen (xr) x len (xc)**, then $ MAXR + MAXC-1 $ is the solution.

E.py

h,w,m=map(int,input().split())
item=[list(map(int,input().split())) for i in range(m)]
row=[0]*h
col=[0]*w
for i in range(m):
    x,y=item[i]
    row[x-1]+=1
    col[y-1]+=1
mr,mc=max(row),max(col)
xr=set([i for i in range(h) if row[i]==mr])
xc=set([i for i in range(w) if col[i]==mc])
check=len(xr)*len(xc)
for i in range(m):
    r,c=item[i]
    if r-1 in xr and c-1 in xc:
        check-=1
print(mr+mc if check>0 else mr+mc-1)

F problem

I got an image of the policy by referring to the explanation, so I will solve it within a few days.