AtCoder Beginner Contest 113 Review of past questions

Time required

スクリーンショット 2020-04-19 9.42.22.png

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)

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions