[PYTHON] AtCoder Beginner Contest 094 Review of past questions

Time required

Impressions

Since I was there before, this is the second past question. I can answer completely if it is at this level, but I want to be able to compete firmly with something at a slightly higher level.

Problem A

Note that it is necessary that a <= x as well as a + b> = x.

answerA.py

a,b,c,d=[int(input()) for i in range(4)]
print(min(a,b)+min(c,d))

B problem

Consider how many tollhouses there are for 1 ~ x and x ~ n respectively. If you count the number of tollhouses from 1 to x, you can also find the number of tollhouses from x to n.

answerB.py

n,m,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in a:
    if i<x:
        ans+=1
    else:
        break
print(min(ans,m-ans))

C problem

Regarding the median, since n is an even number, the n // 2nd number or the n // 2 + 1th number will be the median when numbering 1 to n in ascending order. If the n // 2nd number is omitted from the 1st, the median is the n // 2 + 1th number, and if the n // 2 + 1st to nth number is omitted, n /// The second number is the median. (** I did an experiment and confirmed it. **)

answerC.py

n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
k,l=y[n//2-1],y[n//2]
for i in range(n):
    if x[i]<=k:
        print(l)
    else:
        print(k)

D problem

First, for $ \ _ {a_i} C \ _ {a_j} $, it is clear that when you fix ** $ a \ _j $, the larger $ a \ _i $, the larger **. Therefore, ** $ a \ _i $ is determined to be the largest of a **, so it is only necessary to determine one variable of ** $ a \ _j $ **. Therefore, if $ \ _ {max (a)} C \ _ {a_j} $ is used to calculate the elements of a other than max (a) as $ a_j $ and their magnitudes are compared, the maximum value is O (n). There is a trap here, though it seems to be sought. This is because ** $ \ _ {max (a)} C \ _r $ cannot be calculated with O (1) **. Also, if you make a table for Combination calculation, it will be calculated by O (1), but it will take O (n) to prepare the table, so it will not be in time (n is up to $ 10 ^ 9 $). Therefore, if you are calculating $ \ _ {max (a)} C_r $, you will find that you cannot meet the time limit. Now, let's think about calculating $ a_j $ when ** $ \ _ {max (a)} C \ _ {a_j} $ is the maximum without calculating **. Then you can see that $ a_j $ is maximized as close to n / 2 as possible (I will omit the proof because it is troublesome, but it is difficult to prove it by using $ \ _nC \ _r = \ _nC \ _ {nr} $ It doesn't look like it.) Therefore, the answer is the element of a excluding max (a) that is closest to max (a) / 2. This allowed us to find $ \ _nC \ _r $ without calculating it. Implement the above and get the following code.

answerD.py

n=int(input())
a=sorted(list(map(int,input().split())))
b=a[n-1]
a.pop(n-1)
ans=0
for i in range(n-1):
    if abs(b/2-a[ans])>abs(b/2-a[i]):
        ans=i
print(str(b)+" "+str(a[ans]))