[PYTHON] AtCoder Beginner Contest 182 Review

This time's results

Impressions of this time

This time it was about 10 minutes late. I thought that it would go up to the last minute and submitted it, but it was really last minute. Although I was good at both last time and this time, I was only able to participate late, so I will be humiliated in the contest next week.

F seemed to be able to solve it soon, but after E had solved it, I was thinking while removing the bones of the fish for dinner, so I couldn't do it. It is mortifying.

Also, this time the indent width is 2 instead of the usual 4. Due to various reasons, the environment construction was not in time. If you feel like it, change the width to 4.

Problem A

Output as told. Just subtract.

A.py

a,b=map(int,input().split())
print(2*a+100-b)

Problem B

** Since there are only 2 to 1000 candidates for the maximum number **, just search all. However, it is necessary to have a pair of (greatest common divisor, GCD degree) when performing a full search.

B.py

n=int(input())
a=list(map(int,input().split()))
ans=[2,sum(i%2==0 for i in a)]
for j in range(1000,2,-1):
  x=[j,sum(i%j==0 for i in a)]
  if x[1]>ans[1]:
    ans=[x[0],x[1]]
print(ans[0])

C problem

Since the remainder is 3, the total of ** digits should be a multiple of 3 **. At this time, consider how to select the digits you want to remove by ** saving only the remainder after dividing each digit by 3. Therefore, here we set $ check [i] $: = (the remainder is the number of digits of $ i $).

First, if the total number of digits is 0 from the beginning, 0 is output. In other cases, just ** carefully classify the cases as shown below **.

(1) When the remainder of the total number of digits is 1.

When [1] $ check [1] \ geqq 1 $, $ check [1]-= 1 $ causes the remainder of the total digits to be 0. When [2] $ check [1] \ <1 $, $ check [2]-= 2 $ causes the remainder of the total digits to be 0. [3] In any case, when $ sum (check) = 0 $, any digit is selected and erased, so the subject is not satisfied. At this time, -1 is output. We can also show that under this condition it will be $ check [2] \ <2 $.

(2) When the remainder of the total number of digits is 2.

[1] $ check [2] \ geqq When 1 $, $ check [2]-= 1 $ causes the remainder of the total digits to be 0. When [2] $ check [2] \ <1 $, $ check [1]-= 2 $ causes the remainder of the total digits to be 0. [3] In any case, when $ sum (check) = 0 $, any digit is selected and erased, so the subject is not satisfied. At this time, -1 is output. We can also show that under this condition it will be $ check [1] \ <2 $.

C.py

n=input()
l=len(n)
check=[0]*3
for i in range(l):
  check[int(n[i])%3]+=1
if int(n)%3==0:
  print(0)
elif int(n)%3==1:
  if check[1]>=1:
    check[1]-=1
    if sum(check)==0:
      print(-1)
    else:
      print(1)
  else:
    check[2]-=2
    if sum(check)==0:
      print(-1)
    else:
      print(2)
else:
  if check[2]>=1:
    check[2]-=1
    if sum(check)==0:
      print(-1)
    else:
      print(1)
  else:
    check[1]-=2
    if sum(check)==0:
      print(-1)
    else:
      print(2)

D problem

I misread it ** and misunderstood that each move could only be done completely **. In that case, you do not need to devise anything just to think about the maximum value after taking the cumulative sum twice. Also, prepare two arrays to be used in the following discussion. $ b [i]: = $ ($ i $ th complete travel distance) and $ c [i]: = $ ($ i $ th complete travel distance cumulative).

Here, it is good to consider ** separately when it does not move completely **. In other words, if you have completely moved to the $ i (0 \ <i \ <n-2) $ th, you can move the ** $ i + 1 $ th to the maximum because it can be halfway * *is. In other words, if expressed in an expression, $ (\ sum \ _ {j = 0} ^ {i} b [j]) + c [i] $ is the $ i $ th solution. You can think of this as any $ i $. Therefore, it can be implemented by increasing $ i $ in order while managing the value of $ \ sum \ _ {j = 0} ^ {i} b [j] $. Also, it can be easily implemented by taking the cumulative sum of $ b $. This is the second code.

In addition, since the above does not cover the case where it does not move even once and the case where it moves completely with all movements, the maximum value is calculated by adding these cases.

D.py

n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
c=list(accumulate(b,func=max))
ans=[0,b[0]]
now=b[0]
for i in range(1,n):
  ans.append(now+c[i])
  now+=b[i]
ans.append(now)
print(max(ans))

D_better.py

n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
c=list(accumulate(b,func=max))
d=list(accumulate(b))
ans=[0]+[d[i]+c[i] for i in range(n-1)]+[d[n-1]]
print(max(ans))

E problem

It is a similar subject to HHKB Programming Contest 2020-E Lamps. First, suppose you have a ** block or edge-enclosed part ** of a line. If there is even one ** lamp in this area **, that area will be illuminated. On the contrary, in this case, it will not be illuminated by the lamp. Considering the time of the line, ** the number of squares illuminated in either case is the answer **. In the case of rows and columns, it is sufficient to transpose them, so first consider only the rows.

First, if you want to handle such ** continuous parts together, you can do run-length compression ** (typical). In other words, in the initial state, the square where the lamp is placed is 1, the square where the block is placed is 0, and the square where nothing is placed is -1. At this time, we want to consider the part without blocks, so we can compress ** depending on whether a certain cell is 0. That is, it looks like the figure below.

Then, after compressing as shown in the above figure, ** if the compressed part contains at least one 1, ** the solid line part should be set to 1 (illuminated square). You can also use groupby and specify $ lambda \ x: x == 0 $ for func to perform the compression (Reference). ).

Personally, I think I have to get used to the idea of run-length compression. Also, if I feel like it, I will post a summary article on the issue of run-length compression **.

E.py

from itertools import groupby
h,w,n,m=map(int,input().split())
check1=[[-1]*w for i in range(h)]
check2=[[-1]*h for i in range(w)]
for i in range(n):
  a,b=map(int,input().split())
  check1[a-1][b-1]=1
  check2[b-1][a-1]=1
for i in range(m):
  c,d=map(int,input().split())
  check1[c-1][d-1]=0
  check2[d-1][c-1]=0
#print(check1)
#print(check2)
for i in range(h):
  x=[(key,list(group)) for key,group in groupby(check1[i],key=lambda x:x==0)]
  now=0
  for k,g in x:
    if not k and 1 in g:
      for j in g:
        check1[i][now]=1
        now+=1
    else:
      now+=len(g)
for i in range(w):
  x=[(key,list(group)) for key,group in groupby(check2[i],key=lambda x:x==0)]
  now=0
  for k,g in x:
    if not k and 1 in g:
      for j in g:
        check2[i][now]=1
        now+=1
    else:
      now+=len(g)
ans=0
for i in range(h):
  for j in range(w):
    if check1[i][j]==1 or check2[j][i]==1:
      ans+=1
#print(check1)
#print(check2)
print(ans)

F problem

I don't feel like solving it. I will not solve this time.