AtCoder Beginner Contest 125 Review of past questions

Time required

スクリーンショット 2020-01-14 16.40.05.png

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])

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 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 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 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 069 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 049 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 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 103 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 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 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
AtCoder Beginner Contest 122 Review of past questions
AtCoder Beginner Contest 125 Review of past questions
AtCoder Beginner Contest 109 Review of past questions