HHKB Programming Contest 2020 Review
This time's results
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) $.
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.
(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