[PYTHON] AtCoder Beginner Contest 057 Review of past questions

Past questions solved for the first time

Time required

Impressions

I didn't think I would make such a pena just by misunderstanding It's been terrible for the last two days, so I have to be a little more calm

Problem A

Just output the remainder

answerA.py

a,b=map(int,input().split())
print((a+b)%24)

B problem

Check the checkpoints in order and update

answerB.py

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
cd=[list(map(int,input().split())) for i in range(m)]

def manh(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])

ans=[]
for i in range(n):
    ans_sub=[0,manh(ab[i],cd[0])]
    for j in range(m):
        k=manh(ab[i],cd[j])
        if k<ans_sub[1]:
            ans_sub=[j,k]
    ans.append(ans_sub[0])
for i in range(n):
    print(ans[i]+1)

C problem

At first I misunderstood and wrote the floor in ceil. You can search from the front in the range of $ \ sqrt {n} $.

answerC.py

import math
n=int(input())
l=math.floor(math.sqrt(n))
k=math.floor(math.log10(n))+1

for i in range(2,l+1):
    if n%i==0:
        a,b=i,n//i
        x=max(math.floor(math.log10(a))+1,math.floor(math.log10(b))+1)
        k=min(x,k)
print(k)

Code that was a little faster by using exit

answerC_faster.py

from sys import exit
import math
n=int(input())
l=math.floor(math.sqrt(n))

for i in range(l+1,0,-1):
    if n%i==0:
        a,b=i,n//i
        h=max(a,b)
        k=math.floor(math.log10(h))+1
        print(k)
        exit()

D problem

First of all, it is obvious that you should select the ones with the highest value first, and the ones with the same value will have the same total value ** regardless of which one you select, so sort them in descending order and then use the groupby function. I applied it. Here, when there are A or more elements with the highest value, you can select the elements from among those elements so as to satisfy the condition of A or more and B or less. (I couldn't get rid of the bug at all because I thought that the number of the elements was different from the one I should choose from the elements. ** I took the bug without giving up ** is worthy of evaluation. I know how to solve it, but I made a mistake in writing the code ... When I was about to enter the swamp, I thought I had to review it with the feeling of ** starting over ** ...) Next, when A is larger than the number of the most valuable elements, the average decreases as you select the elements, so you want to reduce the number of elements selected as much as possible. Therefore, it is best to select exactly A, which can be easily obtained by counting the elements in order from the front. (** It would have been easier if I kept the original array with group by ... **) The code written based on the above consideration is as follows. In addition to the above mistakes, this problem was too terrible, ** I tried to use scipy and couldn't use it **, ** I shouldn't break it **. In addition, there are some parts that can be understood when verbalized so far, so I think it is important to ** verbalize the solution **.

answerD.py

import math
#from scipy.special import comb
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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,A,B=map(int,input().split())
v=[int(i) for i in input().split()]
v.sort(reverse=True)
v=groupby(v)

if A<=v[0][1]:
    #This is wrong
    m=min(v[0][1],B)
    co=0
    for i in range(A,m+1):
        #v[0][1]Was m
        co+=combinations_count(v[0][1],i)
    print(v[0][0])
    print(co)
else:
    al=0
    l=len(v)
    C=0
    for i in range(l):
        C+=v[i][1]
        if C<=A:
            al+=(v[i][0]*v[i][1])
        else:
            C-=v[i][1]
            al+=(v[i][0]*(A-C))
            co=combinations_count(v[i][1],A-C)
            #I forgot to break
            break
    print(al/A)
    print(co)