AtCoder Beginner Contest 124 Review of past questions

Time required

スクリーンショット 2020-01-13 13.13.28.png

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)

Recommended Posts

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
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions
AtCoder Beginner Contest 106 Review of past questions