[PYTHON] AtCoder Beginner Contest 102 Review of past questions

Time required

Impressions

I couldn't solve the D problem this time. Patterns I haven't seen much

Problem A

You can divide the case according to whether n is an even number. Specifically, if n is an even number, $ n $ should be output, and if n is an odd number, $ n \ times 2 $ should be output.

answerA.py

n=int(input())
print(n if n%2==0 else n*2)

B problem

Since you only need to find the absolute value of the maximum difference, you can find the difference between the maximum and minimum values.

answerB.py

n=int(input())
a=list(map(int,input().split()))
print(max(a)-min(a))

C problem

Here the unknown is $ b $, so

\begin{eqnarray}
abs(A_1-(b+1))+abs(A_2-(b+2))+…+abs(A_n-(b+n))=abs((A_1-1)-b)+abs((A_2-2)-b)+…+abs((A_n-n)-b)
\end{eqnarray}

I thought about $ b $ by dividing abs. (** Separation of unknowns! **)

Here, if you set $ B_i = A_i-i $, this formula can be rewritten as $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $. Furthermore, sorting the sequence $ B $ does not change the value of $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $, so $ abs for the sorted sequence B Consider the maximum value of (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $.

First, consider that ** expressions that include absolute values remove absolute values **, but how to remove absolute values is $ b \ leqq B_1, B_i \ leqq B_ {i + 1} (1 \ leqq i ) Since it is different for leqq n-1) and B_n \ leqq b $, consider the case of $ b \ leqq B_1 $ here.

Under this,

\begin{eqnarray}
abs(B_1-b)+abs(B_2-b)+…+abs(B_n-b)&=&(b-B_1)+(B_2-b)+…+(B_n-b)\\
&=&(B_1+B_2+…+B_n)+(2-n) \times b-2B_1
\end{eqnarray}

It will be. Therefore, for $ b $, when $ n \ geqq 2 $, it increases monotonically and becomes the minimum at $ b = B_1 $ (it can be easily shown when $ n = 1 $).

Similarly, $ B_i \ leqq B_ {i + 1} (1 \ leqq i \ leqq n-1) $ and $ B_n \ leqq b $ also show monotonicity within that interval. Good $ b $ candidates are $ B_1, B_2,…, B_n $.

We know that there are $ n $ candidates for $ b $, and $ abs (B_1-b) + abs (B_2-b) +… + abs (B_n-b) $ corresponding to each $ b $ is the difference. It can be obtained by O (1) by thinking as follows.

This is ** carefully implemented while paying attention to the handling of the index, as shown below.

answerC.py

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=(i+1)
a.sort()

m,now=sum(a)-2*a[0]+2*a[0]-a[0]*n,sum(a)-2*a[0]+2*a[0]-a[0]*n
for i in range(1,n):
    now=now-(2*(i)*a[i-1]-n*a[i-1])+(-2*a[i]+2*(i+1)*a[i]-n*a[i])
    m=min(now,m)

print(m)

D problem

It was difficult with a pattern I had never done before. After all, I implemented it after seeing the answers of multiple people. Also, in this solution, it was written as the scale method, but I noticed that it had a convexity, so I implemented it with a ternary search **.

First, when you implement it yourself, set $ max (p, q, r, s) -min (p, q, r, s) $ to $ k $ and $ p + q + r + s = $ ( I tried to narrow down the values of $ p, q, r, s $ using the sum of the sequence A), but I couldn't narrow down more corner cases than I expected.

Next, I tried to think about the order of size by $ 4! $, But I couldn't do it at all.

But I forgot that there is one typical policy here. ** If there are multiple unknowns, think fixedly **. In this problem, there are three unknowns (here, the position that divides the subsequence), so let's fix one of them.

Actually, in such ** three patterns, if you fix the center, the section etc. will be narrowed, so it will be easier to find **. Even in this problem, if you fix the partition in the middle, the visibility will improve at once.

When the middle partition is fixed as $ i (1 \ leqq i \ leqq n-1) $ th, $ p $ and $ q $, $ r $ and $ s $ should be as close as possible to $ max (p, p, If you draw a diagram, you can see that q, r, s) -min (p, q, r, s) $ can be made as small as possible. This can actually be proved as follows.

Therefore, in the following we will consider making $ p $ and $ q $ as close as possible, but $ r $ and $ s $ can be thought of in much the same way.

Also, when $ p $ and $ q $ are as close as possible, when the optimal $ p, q $ is bordered by the $ j (1 \ leqq j \ leqq i-1) $ th partition, that ** You can see that $ max (p, q) -min (p, q) $ increases monotonically as you choose a partition away from the $ j $ th partition (the proof here is trivial). I don't.)

Therefore, it can be said that $ max (p, q) -min (p, q) $ has a convexity for the index of the partition **, so the best index for the partition of $ p, q $ is ** You can search by ternary search ** (I will summarize ternary search in another article).

Also, when determining the index of the partition, ** $ p, q $ must be calculated by $ O (1) $ **, but this is ** the cumulative sum is calculated first and the difference is considered **. You can ask for it immediately.

When the above is implemented, it becomes as follows. It was a difficult problem, but it was a very informative one.

answerD.py

n=int(input())
a=list(map(int,input().split()))
s=[a[0]]
for i in range(1,n):
    s.append(s[-1]+a[i])

def f(c,i):
    global n,a,s
    return abs(s[c]-(s[i]-s[c]))

def g(c,i):
    global n,a,s
    return abs((s[c]-s[i])-(s[n-1]-s[c]))

ans=[]
for i in range(1,n-2):
    ans_=[]
    #Decide on the left
    l,r=0,i
    while l+2<r:
        c1=(l*2+r)//3
        c2=(l+2*r)//3
        if f(c1,i)>f(c2,i):
            l=c1
        else:
            r=c2
    x=sorted([(f(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x])
    ans_.append(s[i]-s[x])

    #Decide on the right
    l,r=i+1,n-1
    while l+2<r:
        c1=(l*2+r)//3
        c2=(l+2*r)//3
        if g(c1,i)>g(c2,i):
            l=c1
        else:
            r=c2
    x=sorted([(g(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x]-s[i])
    ans_.append(s[n-1]-s[x])

    ans.append(max(ans_)-min(ans_))
print(min(ans))