[PYTHON] AtCoder Beginner Contest 125 Review of past questions

Time required

Impressions

Past questions solved a few days ago It's typical of Sasuga, so I couldn't solve it

Problem A

It's easy considering how many times biscuits are manufactured.

answerA.py

a,b,t=map(int,input().split())
print(b*(t//a))

B problem

Access in ascending order from the smallest index and count the larger one compared to 0.

answerB.py

n=int(input())
v=input().split()
c=input().split()
co=0
for i in range(n):
    co+=max(0,int(v[i])-int(c[i]))
print(co)

C problem

In the four-question era, the C problem is more difficult than the D problem, isn't it? Well, that's the typical problem ... Since you can select one integer and rewrite it to any number you like, you can find the greatest common divisor of the remaining N-1 integers and think about the maximum value. However, if implemented purely, it will be O ($ N ^ 2 \ times log (maxA) $), which will exceed the constraint with a margin. Here, for some reason (I think I had a bug in my head), I was trying to experiment without a policy or use an appropriate algorithm (such as binary search). While considering the reason why this is not possible, I made the following important discoveries. (Basics in the basics ...)

There is an algorithm to reduce the amount of calculation!

In other words, the first thing to consider in this problem is ** the cause of the large amount of calculation **, and it is easy to notice that ** there is a part that is calculated multiple times in the calculation of gcd . I will. For example, comparing the case of selecting the kth integer and the case of selecting the k + 1th integer, gcd is gcd (gcd ($ A_1 $ ~ $ A_ {k-1} )), gcd ( A_), respectively. {k + 1} $ ~ $ A_ {N} )) and gcd (gcd ( A_1 $ ~ $ A_ {k} ), gcd ( A_ {k + 2} $ ~ $ A_ {N} $) ), So you can see that $ A_1 $ ~ $ A_ {k-1} $ and $ A_ {k + 2} $ ~ $ A_ {N} $ are common. In the same way, considering selecting $ A_1 $ ~ $ A_ {N} $ respectively, considering the cumulative gcd from the left and right, it is not necessary to calculate multiple times, and O ($ N \ times log (maxA)) You can drop the order to $) and calculate. From the above, I was able to easily write a program by implementing the memo phase and the calculation phase separately. ( I have a habit of thinking strangely complicated, so I want to fix it. **)

answerC.py

from fractions import gcd

n=int(input())
a=[int(i) for i in input().split()]
a1=[a[0]]
for i in range(1,n-1):
    a1.append(gcd(a1[-1],a[i]))
a2=[a[-1]]
for i in range(n-2,0,-1):
    a2.append(gcd(a2[-1],a[i]))
m=[]
for i in range(n-2):
    m.append(gcd(a1[i],a2[-i-2]))
m.append(a1[-1])
m.append(a2[-1])
print(max(m))

D problem

First of all, I will also experiment with this. In this problem, we want to maximize the sum, so the idea is to increase the number of positives in the integer sequence as much as possible. Here, if you repeat the experiment, you will find that ** most of the elements can be corrected **. Furthermore, since most of the elements are positive, the operation defined in this problem could ** create an operation that selects any i, j and multiplies $ A_i $ and $ A_j $ by -1 **. I thought. This hypothesis is correct: $ A_i $ and $ A_ {i + 1} $, $ A_ {i + 1} $ and $ A_ {i + 2} $,…, $ A_ {j-2} $ and $ A_ { This can be achieved by performing the operations defined in this problem in the order of j-1} $, $ A_ {j-1} $ and $ A_ {j} $. If the above can be shown, only an even number of negative elements can be made positive, and when there are an even number of negative elements, all can be made positive. When there are an odd number of SUMs, you can find SUM excluding ** the smallest element of absolute value **.

answerD.py

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
j=n
for i in range(n):
    if a[i]>=0:
        j=i
        break
a=list(map(abs,a))
a.sort()
if j%2==0:
    print(sum(a))
else:
    print(sum(a)-2*a[0])