[PYTHON] AtCoder Beginner Contest 081 Review of past questions

Time required

Impressions

I solved the D problem properly twice in a row. I was able to solve it while carefully considering it, but before I knew it, I was solving it while doing FX ... I feel that if I don't control myself, concentrate during the virtual console, and follow the rules firmly, I won't be able to connect to the future.

Problem A

Count how many 1s there are. Initially I used find instead of count. Why don't you even know the basic functions ...

answerA.py

print(input().count("1"))

B problem

Hmm, just write. Consider whether all the elements are divisible by 2. There seems to be a more concise way of writing. (← I have added it because I received a comment.)

answerB.py

n=int(input())
a=list(map(int,input().split()))
ans=0
def check_all():
    global a,n
    for i in range(n):
        if a[i]%2!=0:
            return False
    return True
while check_all():
    ans+=1
    for i in range(n):
        a[i]//=2
print(ans)

Postscript (2020/03/27)

I have posted the two types of solutions I received in the comments. This is the first time I have actually used the function called all, so I would like to use it from now on.

answerB_better.py

n=int(input())
a=list(map(int,input().split()))

ans=0
while all(i%2==0 for i in a):
    ans+=1
    for j in range(n):
        a[j]//=2
print(ans)

answerB_better.py

from functools import reduce
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
x=reduce(gcd,a)

ans=0
while x%2==0:
    ans+=1
    x//=2
print(ans)

C problem

I want to reduce the number of balls to be rewritten, that is, I do not want to rewrite those with many balls with the same number, so sort and put the same number of balls next to each other and then group them with the group by function. After grouping, sort in descending order of the number of balls, and rewrite all the number of balls in the k + 1st and subsequent groups (with 1-index).

answerC.py

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
def groupby():
    global 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
b=groupby()
b.sort(key=lambda x:x[1],reverse=True)
l=len(b)
ans=0
for i in range(k,l):
    ans+=b[i][1]
print(ans)

D problem

First of all, it means that you can decide freely within 2N times, so I will look for a convenient way. First, consider the case where all elements are 0 or more. In this case, you can easily create a sequence that satisfies the condition by ** adding to the element on the right in order from the left ** (up to n-1 times) ($ a_1, a_1). + a_2,…, a_1 + a_2 +… + a_ {n-1} + a_n $.) However, there are negative numbers here, so this method cannot meet the conditions. Therefore, on the contrary, it is assumed that all the elements are 0 or less. In this case, you can see that ** you can do the reverse operation ** (up to n-1 times). From the above consideration, if the pattern is either "all elements are 0 or more" or "all elements are 0 or less", a sequence that satisfies the condition can be created. Therefore, consider ** creating such a pattern within ** n + 1 times **. In order to create such a pattern, we focused on the number with the largest absolute value. If this number is negative, you can add it to all the other elements to make all the other elements negative, and if it is positive, you can make all the other elements positive (up to n-1). Times). Perform the above two operations in order to obtain the following.

answerD.py

n=int(input())
a=list(map(int,input().split()))
c,d=min(a),max(a)
ans=[]
if abs(c)>abs(d):
    c_=a.index(c)
    for i in range(n):
        if i!=c_ and a[i]>0:
            ans.append(str(c_+1)+" "+str(i+1))
    for i in range(n-1,0,-1):
        ans.append(str(i+1)+" "+str(i))
else:
    d_=a.index(d)
    for i in range(n):
        if i!=d_ and a[i]<0:
            ans.append(str(d_+1)+" "+str(i+1))
    for i in range(n-1):
        ans.append(str(i+1)+" "+str(i+2))
l=len(ans)
print(l)
for i in range(l):
    print(ans[i])