Grades

I started about 20 minutes late, so it's actually 17 minutes.

Impressions

This time too, the result was very disappointing. I noticed the C problem and the D problem when I saw the answer, so I think that this level of problem (water, blue diff) is my problem.

Problem A

All you have to do is search all the dates and check them one by one.

`A.py`


m,d=map(int,input().split())
ans=0
for i in range(1,m+1):
    for j in range(22,d+1):
        if j%10>=2 and (j%10)*(j//10)==i:
            ans+=1
print(ans)

B problem

Divide the number of inversions into (1) the number of inversions in the integer sequence $ A $ and (2) the number of inversions between the connected integer sequence $ A $ **.

In case of ① There are $ K $ in the integer sequence $ A $, and if the number of inversions in the integer sequence $ A $ is $ X $, then $ X \ times K $ is the total number of inversions. Also, the number of inversions can be calculated naive by $ O (N) $.

In case of ② The number of elements larger than $ A_i $ in the integer sequence $ A $ can be calculated using bisect_right by sorting the integer sequence $ A $. Assuming that the number of elements is $ Y $, the number of inversions for $ A_i $ in the $ j $ th integer sequence $ A $ is $ Y \ times (j-1) $. Also, considering the sum at $ 1 \ leqq j \ leqq K $, the total number of inversions for $ A_i $ is $ Y \ times k \ times (k-1) \ div 2 $. You can find this for any $ 1 \ leqq i \ leqq N $.

The answer is to find the sum of the cases ① and ② above. Also, the answer can be very large and should be divided by $ 10 ^ 9 + 7 $.

`B.py`


from bisect import bisect_right
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=sorted(a)
mod=10**9+7
ans=0
for i in range(n):
    for j in range(n):
        if i<j and a[i]>a[j]:
            ans+=1
ans*=k
#print(ans)
ans%=mod
r=0
for i in range(n):
    r+=(n-bisect_right(b,b[i]))
ans+=(r*(k-1)*k//2)
ans%=mod
print(ans)

C problem

I often see it in AtCoder, but it's a type of problem that I'm not good at, so I'd like to be able to deal with it. In addition, the $ i $ th color is represented by $ S \ _i $ below.

First, since the interval is selected and the color is inverted, consider ** finding the interval by the difference ** (** the idea of cumulative sum! **). In other words, consider the time when you select the interval $ [l, r] $ and invert the colors. At this time, if it is inverted an even number of times, it will return to its original state, so inverting $ [l, r] $ is equivalent to inverting $ [1, l-1] $ and $ [1, r] $. I will. Therefore, ** $ l $ and $ r $ can be considered independently **, and it is important whether each cell is ** chosen as the left side or the right side of the interval **. Also, I would like to note that there are many ways to think separately on the left and right of the section.

(If you think of the interval in the form of cumulative 〇〇, the amount of calculation will decrease because ** you can pre-calculate independently by separating the interval on the left side and the right side ** !!)

Here, when selecting each cell as the left, consider how to arrange $ L $, and when selecting each cell as the right, consider how to arrange $ L, R $ as $ R $. Also, let the columns of $ L and R $ arranged at this time be $ T $, and focus on ** $ T \ _i $ and $ T \ _ {i + 1} $ to classify the cases **. (The reason for paying attention to the adjacent elements is ** because if the neighbors are uniquely determined, the whole is uniquely determined **. Also, the whole is uniquely determined by ** $ W, B $ in the arrangement of $ There are $ 2 ^ n $ ways to arrange L and R $, and you can see that the arrangement is bijective **.)

① When $ T \ _ {i} = L, T \ _ {i + 1} = L $ $ [I, i] $ is flipped at the same value as selecting and flipping $ [1, i-1] $ and $ [1, i] $. Therefore, it needs to be $ S \ _ {i} \ neq S \ _ {i + 1} $.

② When $ T \ _ {i} = R, T \ _ {i + 1} = R $ $ [I + 1, i + 1] $ is flipped at the same value as selecting and flipping $ [1, i] $ and $ [1, i + 1] $. Therefore, it needs to be $ S \ _ {i} \ neq S \ _ {i + 1} $.

③ When $ T \ _ {i} = L, T \ _ {i + 1} = R $ $ [I, i + 1] $ is flipped at the same value as selecting and flipping $ [1, i-1] $ and $ [1, i + 1] $. Therefore, it is necessary that $ S \ _ {i} = S \ _ {i + 1} $.

④ When $ T \ _ {i} = R, T \ _ {i + 1} = L $ There is no interval to flip with the same value as selecting and flipping $ [1, i] $ and $ [1, i] $. Therefore, it is necessary that $ S \ _ {i} = S \ _ {i + 1} $.

From the above 4 patterns, when $ S \ _ {i} = S \ _ {i + 1} $, $ T \ _ {i} \ neq T \ _ {i + 1} $, $ S \ _ { When i} \ neq S \ _ {i + 1} $, then $ T \ _ {i} = T \ _ {i + 1} $ (this only meets the ** requirements and does not hold) Note that it allows **.).

Also, consider how many combinations of $ L and R $ are in operation based on the arrangement of $ L and R $, but consider ** $ L $ as an open parenthesis and $ R $ as a closing parenthesis. For example, ** First, it is necessary to satisfy the condition that the parenthesized string holds (see ABC167-F). If this condition is met, the combination of $ L and R $ at the time of operation can be obtained by finding the product of ** how many corresponding opening brackets there are by looking at the closing brackets in order from the left side **. Also, there are $ N! $ Ways of operations ** $ N $ times, so this is the solution. Also note that the answer should be found as a remainder of $ 10 ^ 9 + 7 $.

`C.py`


n=int(input())
s=input()
if s[0]=="W":
    exit(print(0))
t=[1]
for i in range(1,2*n):
    if s[i]==s[i-1]:
        t.append(-t[-1])
    else:
        t.append(t[-1])
now=1
for i in range(1,2*n):
    now+=t[i]
    if now<0:
        exit(print(0))
if now!=0:
    exit(print(0))
#The left is left over, so combine when the right comes
ans=1
mod=10**9+7
ca=0
for i in range(2*n):
    if t[i]==1:
        ca+=1
    else:
        ans*=ca
        ans%=mod
        ca-=1
#Ans at this point does not consider the order only for the number of combinations
for i in range(1,n+1):
    ans*=i
    ans%=mod
print(ans)

D problem

** It is a problem that can be seen better by abstracting the problem **. I tend to concentrate on experiments when it comes to construction problems, but I want to be able to solve them with an awareness of abstraction.

First, an even number of passages of the same level when returning through several rooms (in any way) means that there are no odd cycles for passages of the same level **. is. Now consider ** paraphrasing ** that there is no odd cycle. This is obvious as ** thinking about the diagram **, but it can be achieved by ** putting edges only between the bipartite graphs **. If you think of a level as a color scheme, you may be suspicious that it is a bipartite graph because it involves a dot coloring problem and evenness. Also, as you can see from PDF here ** Bipartite graph and no odd cycle are equivalent * * Seems to be a general theorem.

Therefore, consider ** creating a bipartite graph at each level **. In addition, the vertices in each vertex set divided by the bipartite graph are also connected, but for these as well, a bipartite graph must be formed, as shown in the figure below.

Therefore, the maximum value of the level can be minimized by making the vertex set into a bipartite graph, extending edges between the sets, and recursively thinking about the divided sets. So it looks like this (implementation is easy as it only does DFS):

`D.py`


N=int(input())
ans=[[0]*N for j in range(N)]
#n is the length of vec
#Next passage level
def dfs(n,vec,level):
    global ans
    l=vec[:n//2]
    r=vec[n//2:]
    for i in l:
        for j in r:
            ans[i][j]=level
    if len(l)>1:
        dfs(len(l),l,level+1)
    if len(r)>1:
        dfs(len(r),r,level+1)


dfs(N,[i for i in range(N)],1)
for i in range(N-1):
    a=[]
    for j in range(N):
        if i<j:
            a.append(str(ans[i][j]))
    print(" ".join(a))

[PYTHON] 1st Japan's Strongest Programmer Student Championship-Qualifying-Bacha Review (8/8)