[PYTHON] HHKB Programming Contest 2020 Review

This time's results

スクリーンショット 2020-10-11 10.32.48.png

Impressions of this time

It was the second best performer, but I'm disappointed because I'm not aiming here. It's good to skip the D problem and move on to the E problem, but ** I'm disappointed because the D problem should have been solved if I think carefully **.

Problem A

If it is equal to Y, convert it with the upper method.

A.py


s,t=input(),input()
if s=="Y":
    print(t.upper())
else:
    print(t)

B problem

I was impatient because I couldn't read the question sentence. In summary, the problem is to find the number of squares that are not cluttered when you select 2 squares vertically or 2 squares horizontally.

Select 2 squares vertically or 2 squares horizontally. At this time, if you think about it inverted, you can think of the vertical 2 squares as the horizontal 2 squares, so the sum is calculated by judging the horizontal 2 squares of the original matrix and the horizontal 2 squares of the inverted matrix.

B.py


h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
t=[["" for j in range(h)] for i in range(w)]
for i in range(h):
    for j in range(w):
        t[j][i]=s[i][j]
ans=0
for i in range(h):
    for j in range(w-1):
        if s[i][j]=="." and s[i][j+1]==".":
            ans+=1
for i in range(w):
    for j in range(h-1):
        if t[i][j]=="." and t[i][j+1]==".":
            ans+=1
print(ans)

C problem

It is a problem to find $ mex $ that often appears in Kodofo. Hold $ mi $ as an array $ check $ that stores the number that appears up to the $ i $ th and the solution at the $ i $ th point (the minimum value among the numbers that do not appear).

At this time, ** $ mi $ increases monotonically **, so when $ check [mi]! = 0 $, increment until $ mi $ is found, which is $ check [mi] = 0 $, and then $ check. When [mi] = 0 $, $ mi $ should be output.

(I don't think it's that easy, but I'm surprised that many people go through it.)

C.py


n=int(input())
p=list(map(int,input().split()))
check=[0]*200001
mi=0
for i in range(n):
    check[p[i]]+=1
    while True:
        if check[mi]>0:
            mi+=1
        else:
            break
    print(mi)

D problem

First, I misread it as ** to put multiple red squares and blue squares **. Since there is one red square and one blue square, consider finding ** how to arrange the other when one is fixed ** and finding it with $ O (1) $ by transforming the formula. Now consider ** fixing the red square and moving the blue square ** as (one side of the red square: A) $ \ geqq $ (one side of the blue square: B). At this time, it is assumed that the lower left corner of the red square is at $ (i, j) \ (0 \ leqq i \ <N-A, 0 \ leqq i \ <N-A) $.

IMG_0686.jpg

Then, consider the number of cases where a blue square is included in the above red, green, yellow, and blue rectangles. Also, if each of the four ** overlapping parts contains a blue square **, you need to subtract it. Here, the rectangular part and the overlapping part are ** equal to the sum from the symmetry **, so the answer can be obtained by quadrupling the following red rectangle minus the blue rectangle.

IMG_0685.jpg

(1) About the red rectangle Considering the width of the blue square and the blue square, $ B \ leqq i \ leqq N-A $ holds. At this time, the number of blue squares included is

\begin{align}
&\sum_{i,j}(N-B-1)(i-B+1)\\
&=(N-B-1)\sum_{i,j}(i-B+1)\\
&=(N-B-1)\sum_{j}(\sum_{i}(i-B+1))\\
&=(N-B-1)\sum_{j}(1,2,…,N-A-B+1)\\
&=(N-B-1)\sum_{j}\frac{(N-A-B+1)(N-A-B+2)}{2}\\
&=(N-B-1)(N-A+1)\frac{(N-A-B+1)(N-A-B+2)}{2}\\
\end{align}

(2) About the blue rectangle In addition to $ B \ leqq i \ leqq N-A $, $ B \ leqq j \ leqq N-A $ also holds. At this time, the number of blue squares included is

\begin{align}
&\sum_{i,j}(j-B-1)(i-B+1)\\
&=\sum_{i}(i-B+1)\times \sum_{j}(j-B+1)\\
&=(\frac{(N-A-B+1)(N-A-B+2)}{2})^2\\
\end{align}

The above calculation depends on $ (j-B-1), (i-B + 1) $ and ** $ i, j $ respectively **, so we will use the separation as a sum. Note that if one of the terms contains $ i, j $, it cannot be separated.

You can find it by quadrupling the above (1) minus (2). Also, if you use Python, you don't have to worry about overflow because it is a multiple precision integer, and finally find the remainder divided by $ 10 ^ 9 + 7 $.

D.py


mod=10**9+7
for _ in range(int(input())):
    n,a,b=map(int,input().split())
    if a<b:
        a,b=b,a
    x=(n-a-b+1)*(n-a-b+2)//2*(n-a+1)*(n-b+1)*4
    y=((n-a-b+1)*(n-a-b+2)//2)**2*4
    if a+b>n:
        print(0)
        continue
    print((x-y)%mod)

E problem

I'm glad that I was able to move from D immediately in the actual production. I'm glad that the implementation was straightforward without causing too many bugs.

First, since there is a sum, consider how many times the illuminated square appears in $ 2 ^ k $ streets ** (** pay attention to the number of elements! **). Here, the square that is illuminated when the light is placed on a certain square becomes a continuous and uncluttered square from that square. Here, when you illuminate some squares, you may illuminate the squares with multiple lights. At this time, it is necessary to add the cell to the solution as one time, so I assumed that ** the cell is illuminated by $ x $ lights ** and thought about how many times the cell would appear as the illuminated cell. .. Here, if any of ** $ x $ lights are on, that square will be illuminated **. Therefore, there are $ 2 ^ k $ ways to choose the squares to put the proof, and $ 2 ^ {kx} $ ways to choose none of the $ x $ squares, so at least one choice is $ 2 ^ k-2 ^ {kx} $ street ($ \ because $ inclusion principle).

Therefore, the sum can be calculated by $ O (HW) $ by calculating the number of squares illuminated by each square and performing the precalculation of the square. Here, ** the cells that illuminate a certain cell share a row or column **, and if the matrix is transposed, it is the same, so how many cells ** that share a row ** are illuminated? Let's think first.

Here, when there are $ y $ consecutive uncluttered cells in a row, the number of cells that are illuminated by sharing the row for any cell contained in it is $ y $ **. .. Therefore, use the itertools groupby function (reference) to create a continuous, uncluttered cell. By summarizing, $ O (HW) $ can be used to find $ y $ in each cell. Similarly, find out how many of the squares that share a column are illuminated, and subtract 1 from the value added to $ y $ ($ \ because $ ** count that square twice **). Yes) You can find $ x $ in each cell.

E.py


mod=10**9+7
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
k=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            k+=1
t=[["" for j in range(h)] for i in range(w)]
for i in range(h):
    for j in range(w):
        t[j][i]=s[i][j]
po=[0]*(k+1)
po[0]=1
for i in range(1,k+1):
    po[i]=po[i-1]*2
    po[i]%=mod
#The part connected by a line
from itertools import groupby
check=[[0]*w for i in range(h)]
for i in range(h):
    now=0
    for key,group in groupby(s[i]):
        l=len(list(group))
        if key=="#":
            now+=l
        else:
            for j in range(now,now+l):
                check[i][j]+=l
            now+=l
for i in range(w):
    now=0
    for key,group in groupby(t[i]):
        l=len(list(group))
        if key=="#":
            now+=l
        else:
            for j in range(now,now+l):
                check[j][i]+=l
            now+=l
ans=0
for i in range(h):
    for j in range(w):
        #print(k,k-check[i][j])
        if check[i][j]!=0:
            ans+=(po[k]-po[k-check[i][j]+1])
        ans%=mod
print(ans)

F problem

I will skip this time.

Recommended Posts

HHKB Programming Contest 2020 Review
Keyence Programming Contest 2020 Review
Notes for HHKB Programming Contest 2020
AtCoder HHKB Programming Contest 2020 Participation Report
yukicoder contest 259 Review
yukicoder contest 264 Review
Acing Programming Contest 2020
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
Sumitomo Mitsui Trust Bank Programming Contest 2019 Review
AtCoder Beginner Contest 152 Review
AtCoder Grand Contest 041 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 181 Review
After "Diverta 2019 Programming Contest"
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
Keyence Programming Contest 2021 Notes
AtCoder Grand Contest 044 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 176 Review
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
Atcoder Acing Programming Contest Python
atcoder Review of Panasonic Programming Contest 2020, up to question E (Python)
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Beginner Contest 066 Review past questions
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Panasonic Programming Contest 2020 Participation Report
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