[PYTHON] AtCoder Beginner Contest 124 Review of past questions

Time required

Impressions

I got tired of doing problems from 50 to 70, so I tried a completely different number.

Problem A

In other words, always press the larger one

answerA.py

a,b=map(int,input().split())
if a==b:
    print(2*a)
else:
    print(2*max(a,b)-1)

B problem

Make sure you can actually see it from each inn. Cases should be classified according to whether or not there is an inn larger than the inn on the sea side.

answerB.py

n=int(input())
h=list(map(int,input().split()))
c=0
for i in range(n):
    for j in range(i):
        if h[j]>h[i]:
            break
    else:
        c+=1
print(c)

C problem

It is good to ** pay attention to the final state ** for such problems of the repainting system. Since there can be only either 010101 ... or 101010 ..., try both and solve the one with a small number of rewrites.

answerC.py

s=input()
l=len(s)
sa=""
sb=""
for i in range(l):
    if i%2==0:
        sa+="0"
        sb+="1"
    else:
        sa+="1"
        sb+="0"
ca=0
cb=0
for i in range(l):
    if sa[i]!=s[i]:
        ca+=1
    if sb[i]!=s[i]:
        cb+=1
#print(ca)
#print(cb)
print(min(ca,cb))

D problem

In this problem, as you can see from the experiment with the sample, ** n times of instructions can be used to make a handstand for n consecutive people **. If you refer to (Kenchon's article, it is true that ** operations on intersecting sections are for non-intersecting sections. You can see that the operation is equivalent to the split operation **.) Therefore, we know that we should find the total number of people in k consecutive places, and we can see that it would be better to combine the people in each consecutive place into one with the groupby function. Here, the return value of the groupby function is [[0, n1], [1, n2], ....] or [[1, n1], [0, n2], ....] \ (array G). , N1, n2 .... are in the form of either (the number of consecutive people). Furthermore, in order to take K consecutive people from array G so that the total number of consecutive people becomes large, the operation of changing 0 to 1 corresponds to a handstand, so it starts with ** 1 and ends with 1. You can also see that you can fetch 2K + 1 elements like this from the array G **. However, the first pattern of the return value cannot fetch 2K + 1 elements that start with 1 and end with 1 (including the first element) because the first element is 0. So, if you choose the K part that contains the first 0 as the part to change, you will think of 2K elements that start with 0 and end with 1 (including the first element). And after that, you can ** reduce to the second pattern by thinking except for the first 0 **. Also, when considering the second pattern, ** shift the elements by two ** and ** the last element may be 0 **, so in that case it is necessary to separate the cases. Caution is required. When the above is implemented, it becomes as follows. (It was too complicated and the implementation was tight, and the judgment conditions were set appropriately, so it took a long time to debug.)

answerD.py

from sys import exit
#groupby function definition
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n,k=map(int,input().split())
s=list(input())
#Apply the groupby function"0"When"1"Record how many of each are lined up in a row
x=groupby(s)
l=len(x)
#sum(y)I wanted to make it easier
y=[x[i][1] for i in range(l)]

#Reduced to the second pattern of return values of the groupby function
if x[0][0]=="0":
    su=sum(y[:2*k])
    ans=su
    y.pop(0)
    #Since it will be deleted, l-Don't forget to
    l-=1
else:
    ans=0
#First 2k+Consider the sum of one.(Since we will count from here by the scale method)
su=sum(y[:2*k+1])
#Don't forget to update ans
ans=max(ans,su)
#Don't forget to divide by 2 as you will take two scales each
l_sub=(l-(2*k+1))//2
#2k+There may not be more than one, so at this point max is known.
if l_sub<=0:
    print(ans)
    exit()
#Actually take the scale and follow to the last element
for i in range(l_sub):
    #Take two scales
    su-=y[2*i]
    su-=y[2*i+1]
    su+=y[2*k+1+(2*i)]
    su+=y[2*k+1+(2*i+1)]
    ans=max(su,ans)
#If the last element is 0, the following conditions are met
#Note that in this case it starts with 1 and ends with 0(You can subtract twice and add only once)
if 2*k+1+2*l_sub<l:
    su-=y[2*l_sub]
    su-=y[2*l_sub+1]
    su+=y[2*k+1+2*l_sub]
    ans=max(su,ans)
print(ans)