[PYTHON] AtCoder Beginner Contest 113 Review of past questions

Time required

Impressions

"D problem is difficult, I don't know!", But when I reviewed it, it was a DP that was nothing. I've been making a lot of mistakes recently that I can't reach the idea of DP due to the problem of state transition, so I will never do it next time.

Problem A

y is half price.

answerA.py

x,y=map(int,input().split())
print(x+y//2)

B problem

The number closest to A is the number with the smallest absolute difference from A. Also, since you are looking for the point number, you also need to save the point number.

answerB.py

n=int(input())
t,a=map(int,input().split())
h=[t-int(i)*0.006 for i in input().split()]
ans=[-1,1000000000]
for i in range(n):
    if abs(h[i]-a)<abs(ans[1]-a):
        ans=[i,h[i]]
print(ans[0]+1)

C problem

The output is a combination of the number of the prefecture to which you belong and the number of births in that city. Therefore, first of all, it is necessary to divide the city by prefecture. Also, since it is necessary to output in the order originally received by input in the end, divide it into arrays for each city and put a set of the year of birth and the order received by the first input in each array. .. Under this, arrange the array for each prefecture in the order of birth, combine it with the prefecture number, and insert it into the output array together with the order received by the first input, and at the last output, You can output in the order ** received by the first input **.

answerC.py

n,m=map(int,input().split())
pyi=[[] for i in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    pyi[p-1].append([y,i])
ans=[]
for i in range(n):
    pyi[i].sort()
    for j in range(len(pyi[i])):
        ans.append([(6-len(str(i+1)))*"0"+str(i+1)+(6-len(str(j+1)))*"0"+str(j+1),pyi[i][j][1]])
ans.sort(key=lambda x:x[1])
for i in range(m):
    print(ans[i][0])

D problem

First of all, I tried to search for Mida with bfs and dfs, but I do not know how to decide the arrangement of horizontal lines that do not pass ** and ** that the calculation is not in time because it can be more than ** $ 10 ^ 9 + 7 $. ** So I gave up. First of all, since Amidakuji moves from top to bottom, the idea is that ** it is possible to formulate a recurrence formula by moving from top to bottom ** (I had this idea). ** DP ** is the most compatible with the recurrence formula, and we will consider a policy using DP. Now, let's assume that you are on the vertical line at the position of X cm from the top, and consider which horizontal line you can move to at the position of X + 1 cm. Then, ** you can only move to the next horizontal line ** and you cannot move to a horizontal line farther away. Therefore, since we know how to move, let the element of dp be dp [X] [i], and let it be the number ** when it is at the position of the ith vertical line from the left in ** Xcm (0-indexed). Also, dp [x + 1] [i] is determined only from dp [x] [i-1], dp [x] [i], dp [x] [i + 1]. Here, I would like to consider a combination of ** non-passing (irrelevant) horizontal lines ** when I know the horizontal lines that pass in Xcm, but I found it difficult to consider the passing horizontal lines and the non-passing horizontal lines separately. It was. Therefore, noting that w is extremely small (w $ \ leqq $ 8) and that we can ** consider all combinations of horizontal lines in a full search **, the condition (both two horizontal bars share endpoints). If the horizontal lines are connected to i-1 → i, add dp [x] [i-1] to dp [x + 1] [i], and i + 1 → i If the horizontal line is connected to, add dp [x] [i + 1] to dp [x + 1] [i], and if neither the horizontal line of i-1 → i nor the horizontal line of i + 1 → i is connected If you add dp [x] [i] to dp [x + 1] [i], you can do DP by O ($ HW2 ^ W $). And since the vertical bar to reach is the K (K-1 if it is 0-indexed), you can find dp [H] [K-1].

answerD.py

mod=10**9+7
h,w,K=map(int,input().split())
dp=[[0]*w for j in range(h+1)]
dp[0][0]=1
for i in range(1,h+1):
    for k in range(2**(w-1)):
        for l in range(w-2):
            if ((k>>l)&1) and ((k>>(l+1))&1):
                break
        else:
            for l in range(w):
                if l==0:
                    if ((k>>l)&1):
                        dp[i][l+1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                elif l==w-1:
                    if ((k>>(l-1))&1):
                        dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                else:
                    if ((k>>l)&1) or ((k>>(l-1))&1):
                        if ((k>>l)&1):
                            dp[i][l+1]+=dp[i-1][l]
                        else:
                            dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
print(dp[h][K-1]%mod)