AtCoder Beginner Contest 182 Review

This time's results

スクリーンショット 2020-11-08 23.47.47 1.png

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.

FBE9A326-7DB8-4791-89BC-B587772E999D.jpeg

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.

Recommended Posts

AtCoder Beginner Contest 152 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 Beginner Contest 181 Review
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
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 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 Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 181 Note
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 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 054 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 105 Review of past questions