Problem:


Score : 800 points

Problem Statement

There are N positive integers A_1, A_2, ..., A_N.
Takahashi can perform the following operation on these integers any number of times:

Choose 1 \leq i \leq N and multiply the value of A_i by -2.

Notice that he multiplies it by minus two.

He would like to make A_1 \leq A_2 \leq ... \leq A_N holds.
Find the minimum number of operations required. If it is impossible, print -1.

Constraints

1 \leq N \leq 200000

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the answer.

Sample Input 1

4
3 1 4 1

Sample Output 1

3

One possible solution is:

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now 3, 1, 4, -2.

Choose i=1 and multiply the value of A_1 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, -2.

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, 4.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

0

A_1 \leq A_2 \leq ... \leq A_N holds before any operation is performed.

Sample Input 3

8
657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097

Sample Output 3

7



Sample input:
4
3 1 4 1


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
def main():
    import random,time
    from math import log,ceil

    N=int(input())

    A=list(map(int,input().split()))
    start=time.time()
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=float("inf")
    Init=[i for i in range(N)]
    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    #セグメント木
    #####segfunc######
    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)

    def init(init_val):
        #set_val
        for i in range(n):
            seg[i+num-1]=init_val[i]
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

    #####単位元######
    ide_ele = N

    #num:n以上の最小の2のべき乗
    n=N
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num

    for i in range(1,N):
        c=max(0,ceil(A[i-1]-A[i]))
        ope[i]+=c
        A[i]+=c

    init(Init)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        c=max(0,ceil(B[i-1]-B[i]))
        ope[i]+=c
        S+=c
        B[i]+=c
    #print(time.time()-start)
    init(Init)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    zero_append=zero.append
    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero_append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import random,time
from math import log,ceil

N=int(input())

A=list(map(int,input().split()))
start=time.time()
A=[log(A[i],4) for i in range(N)]
B=[A[-i-1] for i in range(N)]
memo=[0]*(N-1)
ans=float("inf")
Init=[i for i in range(N)]
ope=[0 for i in range(N+1)]
ope[N]=10**20
#セグメント木
#####segfunc######
def segfunc(x,y):
    if ope[x]>ope[y]:
        return y
    elif ope[y]>ope[x]:
        return x
    else:
        return min(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = N

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

for i in range(1,N):
    c=max(0,ceil(A[i-1]-A[i]))
    ope[i]+=c
    A[i]+=c

init(Init)

S=sum(ope[i] for i in range(N))
ans=min(ans,2*S)
zero=[N]

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)
#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,N):
    while i!=zero[-1]:
        k=query(i,zero[-1])
        val=ope[k]+BIT_query(k+1)
        S-=val*(zero[-1]-i)
        BIT_update(i+1,-val)
        BIT_update(zero[-1]+1,val)
        zero.append(k)
    zero.pop()
    memo[i-1]+=2*S

ope=[0 for i in range(N+1)]
ope[N]=10**20
S=0
for i in range(1,N):
    c=max(0,ceil(B[i-1]-B[i]))
    ope[i]+=c
    S+=c
    B[i]+=c
#print(time.time()-start)
init(Init)
#print(time.time()-start)

ans=min(ans,2*S+N)
zero=[N]
BIT=[0]*(n+1)

zero_append=zero.append
for i in range(1,N):
    while i!=zero[-1]:
        k=query(i,zero[-1])
        val=ope[k]+BIT_query(k+1)
        S-=val*(zero[-1]-i)
        BIT_update(i+1,-val)
        BIT_update(zero[-1]+1,val)
        zero_append(k)
    zero.pop()
    memo[N-1-i]+=2*S+(N-i)
#print(time.time()-start)
test=min(memo)
print(min(test,ans))

Submission status: Time Limit Exceeded

Solution code:
import random,time
from math import log,ceil


def four(a,b):
    if b>=a:
        return 0
    else:
        return ceil(a-b)


N=int(input())

A=list(map(int,input().split()))
start=time.time()
A=[log(A[i],4) for i in range(N)]
B=[A[-i-1] for i in range(N)]


#セグメント木
#####segfunc######
def segfunc(x,y):
    if x[0]>y[0]:
        return y
    elif x[0]<y[0]:
        return x
    else:
        return (x[0],min(x[1],y[1]))

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = (float("inf"),10**20)

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

Init=[[0,i] for i in range(N)]
for i in range(1,N):
    c=four(A[i-1],A[i])
    Init[i][0]+=c
    A[i]+=c

init(Init)

plu=[0]*N
plu[0]=sum(Init[i][0] for i in range(N))
S=plu[0]
zero=[N]

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)
#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,N):
    while i!=zero[-1]:
        k=query(i,zero[-1])[1]
        val=Init[k][0]+BIT_query(k+1)
        S-=val*(zero[-1]-i)
        BIT_update(i+1,-val)
        BIT_update(zero[-1]+1,val)
        zero.append(k)
    zero.pop()
    plu[i]=S

Init=[[0,i] for i in range(N)]
S=0
for i in range(1,N):
    c=max(0,ceil(B[i-1]-B[i]))
    Init[i][0]+=c
    S+=c
    B[i]+=c
#print(time.time()-start)
init(Init)
#print(time.time()-start)
neg=[0]*N
neg[0]=S
zero=[N]
check=[]
BIT=[0]*(n+1)

for i in range(1,N):
    while i!=zero[-1]:
        k=query(i,zero[-1])[1]
        val=Init[k][0]+BIT_query(k+1)
        S-=val*(zero[-1]-i)
        BIT_update(i+1,-val)
        BIT_update(zero[-1]+1,val)
        zero.append(k)
    zero.pop()
    neg[i]=S
#print(time.time()-start)
neg=neg[::-1]
for i in range(N):
    plu[i]*=2
    neg[i]=2*neg[i]+(i+1)

ans=min(neg[-1],plu[0])
for i in range(0,N-1):
    test=neg[i]+plu[i+1]
    ans=min(ans,test)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def four(a,b):
    count=0
    while a>b:
        b*=4
        count+=1
    return count

N=int(input())
A=list(map(int,input().split()))
B=[A[-i-1] for i in range(N)]

#セグメント木
#####segfunc######
def segfunc(x,y):
    if x[0]>y[0]:
        return y
    elif x[0]<y[0]:
        return x
    else:
        return (x[0],min(x[1],y[1]))

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = (float("inf"),10**20)

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

Init=[[0,i] for i in range(N)]
for i in range(1,N):
    c=four(A[i-1],A[i])
    Init[i][0]+=c
    A[i]*=4**c

init(Init)

plu=[0]*N
plu[0]=sum(Init[i][0] for i in range(N))
S=plu[0]
zero=[N]

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,N):
    while i!=zero[-1]:
        j=zero[-1]-1
        k=query(i,j+1)[1]
        val=Init[k][0]+BIT_query(k+1)
        S-=val*(j-i+1)
        BIT_update(i+1,-val)
        BIT_update(j+2,val)
        zero.append(k)
    zero.pop()
    plu[i]=S


Init=[[0,i] for i in range(N)]
for i in range(1,N):
    c=four(B[i-1],B[i])
    Init[i][0]+=c
    B[i]*=4**c

init(Init)

neg=[0]*N
neg[0]=sum(Init[i][0] for i in range(N))
S=neg[0]
zero=[N]

BIT=[0]*(n+1)

for i in range(1,N):
    while i!=zero[-1]:
        j=zero[-1]-1
        k=query(i,j+1)[1]
        val=Init[k][0]+BIT_query(k+1)
        S-=val*(j-i+1)
        BIT_update(i+1,-val)
        BIT_update(j+2,val)
        zero.append(k)
    zero.pop()
    neg[i]=S

neg=neg[::-1]
for i in range(N):
    plu[i]*=2
    neg[i]=2*neg[i]+(i+1)

ans=min(neg[-1],plu[0])
for i in range(0,N-1):
    test=neg[i]+plu[i+1]
    ans=min(ans,test)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**10
n = int(input())
a = list(map(int, input().split()))

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	k = -30
	while a[i-1] * pow(4, k) < a[i]:
		k += 1
	for j in range(20):
		if j+k < 20:
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j+k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	k = -30
	while a[i+1] * pow(4, k) < a[i]:
		k += 1
	for j in range(20):
		if j+k < 20:
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j+k, 0)]

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c

まさか、3分探索か？？？
正負が変わる位置を決め撃ったら、あとは貪欲に決まる
正負が変わる位置を1だけ右に変更したとする
すると、基準点より左は回数は単調増加し、右は単調減少する

→3分探索可能そう！！
数字がでかくなりすぎるから根本的な問題か？
C++だと longlongを突破しそう…

4を何回掛ければ左の数以上になるか、を持っておく？
3回のとき、
左に4**N がかかっていれば、4**(N+3)を掛けて対応できる

おなじになるとき、逆向きは-xにしておけばよい
そうでないときは-x+1でおｋ

3分探索が誤りぽさそう？
だとしたら全探索の高速化にかじを切る必要がある

===答えを見た===

いまいち実装がわからない
S[x][i] = i+S[x+1][?]
?が15以上は15から求められる

"""

N = int(input())
A = list(map(int,input().split()))

LS = []
for i in range(N):

    if i == 0:
        now = [i for i in range(16)]
    else:
        now = []

        for j in range(16):

            l = -1
            r = 100

            while r-l != 1:
                m = (l+r)//2
                if A[i-1] * (4**m) >= A[i] * (4**j):
                    r = m
                else:
                    l = m

            if r <= 15:
                now.append(LS[-1][r] + j)
            else:
                now.append(LS[-1][15] + i*(r-15 + r-15+i-1)//2 + j)
        
    LS.append(now)

A.reverse()
RS = []

for i in range(N):

    if i == 0:
        now = [i for i in range(16)]
    else:
        now = []

        for j in range(16):

            l = -1
            r = 100

            while r-l != 1:
                m = (l+r)//2
                if A[i-1] * (4**m) >= A[i] * (4**j):
                    r = m
                else:
                    l = m

            if r <= 15:
                now.append(RS[-1][r] + j)
            else:
                now.append(RS[-1][15] + i*(r-15 + r-15+i-1)//2 + j)
        
    RS.append(now)
RS.reverse()

#print (LS)
#print (RS)

ans = float("inf")

for i in range(N+1):

    if i == 0:
        nn = RS[0][0] * 2
    elif i == N:
        nn = N+LS[-1][0] * 2
    else:
        nn = RS[i][0]*2 + i + LS[i-1][0]*2

    #print (nn)
    ans = min(nn,ans)

print (ans)

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c

まさか、3分探索か？？？
正負が変わる位置を決め撃ったら、あとは貪欲に決まる
正負が変わる位置を1だけ右に変更したとする
すると、基準点より左は回数は単調増加し、右は単調減少する

→3分探索可能そう！！
"""

def want(ind):

    ret = 0
    last = 0
    for i in range(ind,N):

        #print (last)

        if last <= a[i]:
            last = a[i]
        else:
            nb = format(last//a[i],"b")
            #print (nb)

            if len(nb)%2==0:
                ret += len(nb)
                last = a[i] * pow(2,len(nb))
            else:
                if last % a[i] == 0 and pow(2,len(nb)-1) == last//a[i]:
                    ret += len(nb)-1
                    last = a[i] * pow(2,len(nb)-1)
                else:
                    ret += len(nb)+1
                    last = a[i] * pow(2,len(nb)+1)

    last = 0
    for i in range(ind-1,-1,-1):

        ret += 1

        if last <= a[i]:
            last = a[i]
        else:
            nb = format(last//a[i],"b")

            if len(nb)%2==0:
                ret += len(nb)
                last = a[i] * pow(2,len(nb))
            else:
                if last % a[i] == 0 and pow(2,len(nb)-1) == last//a[i]:
                    ret += len(nb)-1
                    last = a[i] * pow(2,len(nb)-1)
                else:
                    ret += len(nb)+1
                    last = a[i] * pow(2,len(nb)+1)       
    
    return ret

N = int(input())

a = list(map(int,input().split()))

l = -1
r = N+2

while r-l > 2:

    m1 = (l*2+r)//3
    m2 = (l+r*2)//3

    r1 = want(m1)
    r2 = want(m2)

    if r1 < r2:
        r = m2
    else:
        l = m1

ans = float("inf")
for i in range(l-3,r+3):

    if i < 0 or i > N+1:
        continue
    ans = min(ans , want(i))

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    dp_base = np.arange(16, dtype=np.int64)
    dp = dp_base.copy()
    result = [0, 0]

    next_a = aaa[-1]
    for i in range(n - 2, -1, -1):
        ndp = dp_base.copy()

        a = aaa[i]
        if a > next_a:
            cnt = 0  # a[i]以上になるためにa[i+1]に4をかけなければならない最小回数
            b = next_a
            while a > b:
                b <<= 2
                cnt += 1
            ndp[:-cnt] += dp[cnt:]
            ndp[-cnt:] += dp[-1] + dp_base[1:cnt + 1] * (n - i - 1)
        else:
            cnt = 0  # a[i]に4をかけても次に影響が出ない最大回数
            b = a
            while next_a >= b:
                b <<= 2
                cnt += 1
            cnt -= 1
            ndp[:cnt] += dp[0]
            ndp[cnt:] += dp[:16 - cnt]
        next_a = a
        result.append(ndp[0])
        dp = ndp
    result.reverse()
    return np.array(result)


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    mul4dp = (fdp + bdp) * 2
    return (mul4dp + np.arange(n + 1)).min()


def test():
    import random
    n = 200000
    aaa = random.choices(range(1, 10 ** 9), k=n)
    print(n)
    print(aaa)
    print(solve(n, aaa))


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    dp = np.array([list(range(16))] * (n + 1), dtype=np.int64)
    arg = np.arange(1, n + 1, dtype=np.int64)

    next_a = aaa[-1]
    for i in range(n - 2, -1, -1):
        a = aaa[i]
        if a > next_a:
            cnt = 0  # a[i]以上になるためにa[i+1]に4をかけなければならない最小回数
            b = next_a
            while a > b:
                b <<= 2
                cnt += 1
            dp[i, :-cnt] += dp[i + 1, cnt:]
            dp[i, -cnt:] += dp[i + 1, -1] + arg[:cnt] * (n - i - 1)
        else:
            cnt = 0  # a[i]に4をかけても次に影響が出ない最大回数
            b = a
            while next_a >= b:
                b <<= 2
                cnt += 1
            cnt -= 1
            dp[i, :cnt] += dp[i + 1, 0]
            dp[i, cnt:] += dp[i + 1, :16 - cnt]
        next_a = a
    return dp


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    mul4dp = (fdp.T[0] + bdp.T[0]) * 2
    return (mul4dp + np.arange(n + 1)).min()


def test():
    import random
    n = 200000
    aaa = random.choices(range(1, 10 ** 9), k=n)
    print(n)
    print(aaa)
    print(solve(n, aaa))


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    dp = np.array([list(range(16))] * (n + 1), dtype=np.int64)

    next_a = aaa[-1]
    for i in range(n - 2, -1, -1):
        a = aaa[i]
        if a > next_a:
            cnt = 0  # a[i]以上になるためにa[i+1]に4をかけなければならない最小回数
            b = next_a
            while a > b:
                b <<= 2
                cnt += 1
            dp[i, :-cnt] += dp[i + 1, cnt:]
            dp[i, -cnt:] += dp[i + 1, -1] + np.arange(1, cnt + 1) * (n - i - 1)
        else:
            cnt = 0  # a[i]に4をかけても次に影響が出ない最大回数
            b = a
            while next_a >= b:
                b <<= 2
                cnt += 1
            cnt -= 1
            dp[i, :cnt] += dp[i + 1, 0]
            dp[i, cnt:] += dp[i + 1, :16 - cnt]
        next_a = a
    return dp


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    mul4dp = (fdp.T[0] + bdp.T[0]) * 2
    return (mul4dp + np.arange(n + 1)).min()


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np


def calc_mul4_dp(n, aaa):
    dp = np.array([list(range(16))] * (n + 1), dtype=np.int64)

    next_a = aaa[-1]
    for i in range(n - 2, -1, -1):
        a = aaa[i]
        if a > next_a:
            cnt = 0  # a[i]以上になるためにa[i+1]に4をかけなければならない最小回数
            b = next_a
            while a > b:
                b <<= 2
                cnt += 1
            print('a > na', cnt, file=sys.stderr)
            dp[i, :-cnt] += dp[i + 1, cnt:]
            dp[i, -cnt:] += dp[i + 1, -1] + np.arange(1, cnt + 1) * (n - i - 1)
        else:
            cnt = 0  # a[i]に4をかけても次に影響が出ない最大回数
            b = a
            while next_a >= b:
                b <<= 2
                cnt += 1
            cnt -= 1
            print('a < na', cnt, file=sys.stderr)
            dp[i, :cnt] += dp[i + 1, 0]
            dp[i, cnt:] += dp[i + 1, :16 - cnt]
        next_a = a
    print(dp, file=sys.stderr)
    return dp


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    mul4dp = (fdp.T[0] + bdp.T[0]) * 2
    print(mul4dp, file=sys.stderr)
    return (mul4dp + np.arange(n + 1)).min()


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,log
N=int(input())
A=[int(i) for i in input().split()]
def f(A):
    dp=[[0]*16 for i in range(N)]
    for i in range(16):
        dp[N-1][i]=i
    for n in range(N-2,-1,-1):
        nx=ceil(log(A[n]/A[n+1])/log(4)) #A
        for x in range(16):
            dx=nx+x
            if dx <=15:
                #print(max(0,dx))
                dp[n][x]=dp[n+1][max(0,dx)]+x
            else:
                dp[n][x]=dp[n+1][15]+x+(N-1-n)*(dx-15)
    L=[0]*N
    for i in range(N):
        L[i]=dp[i][0]
    return L

K=f(A)+[0]
L=[0]+f(A[::-1])[::-1]
ans=10**9
for i in range(N):
    ans=min(ans,i+2*L[i]+2*K[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import log, ceil


def create_dp_table(aaa):
    dp = [list(range(0, 31, 2)) for _ in range(n)]
    dpp = dp[0]
    for i in range(1, n):
        ds = ceil(log(aaa[i] / aaa[i - 1], 4))
        dpi = dp[i]
        for j in range(16):
            k = j + ds
            if k < 16:
                dpi[j] += dpp[max(0, k)]
            else:
                dpi[j] += dpp[15] + (k - 15) * (i + 1)
        dpp = dpi
    return dp


def search_min(neg, pos):
    ret = min(n + neg[-1][0], pos[0][0])
    for i in range(1, n):
        ret = min(ret, i + neg[i - 1][0] + pos[i][0])
    return ret


n = int(input())
aaa = list(map(int, input().split()))
neg = create_dp_table(aaa)
aaa.reverse()
pos = create_dp_table(aaa)
pos.reverse()
print(search_min(neg, pos))

Submission status: Time Limit Exceeded

Solution code:
from math import log, ceil


def create_dp_table(aaa):
    dp = [list(range(16)) for _ in range(n)]
    for i, (pa, a, dpp, dpi) in enumerate(zip(aaa, aaa[1:], dp, dp[1:])):
        ds = ceil(log(a / pa, 4))
        for j in range(16):
            k = j + ds
            if k < 16:
                dpi[j] += dpp[max(0, k)]
            else:
                dpi[j] += dpp[15] + (k - 15) * (i + 1)
    return dp


def search_min(neg, pos):
    ret = min(n + neg[-1][0] * 2, pos[0][0] * 2)
    for i in range(1, n):
        ret = min(ret, i + neg[i - 1][0] * 2 + pos[i][0] * 2)
    return ret


n = int(input())
aaa = list(map(int, input().split()))
neg = create_dp_table(aaa)
pos = create_dp_table(list(reversed(aaa)))
pos.reverse()
print(search_min(neg, pos))

Submission status: Time Limit Exceeded

Solution code:
import sys


def split_list(A):
    sorted_A = sorted(A)
    indexes = [i for i, a in enumerate(A) if A[i] != sorted_A[i]]
    return indexes[0], indexes[-1]


input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
c = 0
ind = 0
rev_ind = -1
kk = 0
while A != sorted(A):
    ind, rev_ind = split_list(A)
    if ind + 1 != rev_ind:
        A[ind] *= -2
        c += 1
    A[rev_ind] *= 4
    c += 2
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
c = 0
ind = 0
rev_ind = -1
while A != sorted(A):
    if A[ind] > A[ind + 1]:
        A[ind] *= -2
        c += 1
    else:
        ind += 1
    if ind > N + rev_ind:
        ind = 0
        rev_ind = -1
    if A[rev_ind] < A[rev_ind - 1]:
        A[rev_ind] *= 4
        c += 2
    else:
        rev_ind -= 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2

def max2(x, y): return x if x >= y else y

def getNums(As, N):
    dp = list(range(16))
    nums = [0] * N
    for i in reversed(range(N - 1)):
        dx = ceil( log2( As[i] / As[i+1] ) / 2 )
        dp2 = [0] * 16
        for x in range(16):
            nx = x + dx
            if nx <= 15:
                dp2[x] = dp[max2(0, nx)] + x
            else:
                dp2[x] = dp[15] + x + (N - 1 - i) * (nx - 15)
        dp = dp2
        nums[i] = dp[0]
    return nums

N = int(input())
As = list(map(int, input().split()))

numPstvs = getNums(As, N)
numNgtvs = getNums(As[::-1], N)[::-1]

ans = float('inf')
for i, (p, m) in enumerate(zip(numPstvs + [0], [0] + numNgtvs)):
    ans = min(ans, 2 * p + 2 * m + i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,log
N = int(input())
A = list(map(int,input().split(" ")))
A2 = list(map(lambda x: x*(-2),A))
dp1 = [ [0]*16 for _ in range(N) ]
dp2 = [ [0]*16 for _ in range(N) ]
pow4 = [ pow(4,x) for x in range(16) ]

for x in range(16):
    dp1[-1][x] = x
    dp2[0][x] = x
for l in range(N-2,-1,-1):
    for x in range(16):
        if pow4[x]*A[l] <= A[l+1]:
            dp1[l][x] = dp1[l+1][0] + x
        else:
            k = ceil(log(pow4[x]*A[l]/A[l+1],4))
            if k > 15:
                dp1[l][x] = dp1[l+1][15] + (N-l+1)*(k-15)
            else:
                dp1[l][x] = dp1[l+1][k] + x

for l in range(1,N):
    for x in range(16):
        if pow4[x]*A2[l] >= A2[l-1]:
            dp2[l][x] = dp2[l-1][0] + x
        else:
            k = ceil(log(pow4[x]*A2[l]/A2[l-1],4))
            if k > 15:
                dp2[l][x] = dp2[l-1][15] + (l+1)*(k -15)
            else:
                dp2[l][x] = dp2[l-1][k] + x


ans = min(2*dp1[0][0],2*dp2[N-1][0]+N)
for i in range(1,N-1):
    ans = min(ans,i+2*(dp1[i][0]+dp2[i-1][0]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,log
N = int(input())
A = list(map(int,input().split(" ")))
A2 = list(map(lambda x: x*(-2),A))
dp1 = [ [0]*16 for _ in range(N) ]
dp2 = [ [0]*16 for _ in range(N) ]

for x in range(16):
    dp1[-1][x] = x
    dp2[0][x] = x
for l in range(N-2,-1,-1):
    for x in range(16):
        if pow(4,x)*A[l] <= A[l+1]:
            dp1[l][x] = dp1[l+1][0] + x
        else:
            k = ceil(log(pow(4,x)*A[l]/A[l+1],4))
            if k > 15:
                dp1[l][x] = dp1[l+1][15] + (N-l+1)*(k-15)
            else:
                dp1[l][x] = dp1[l+1][k] + x

for l in range(1,N):
    for x in range(16):
        if pow(4,x)*A2[l] >= A2[l-1]:
            dp2[l][x] = dp2[l-1][0] + x
        else:
            k = ceil(log(pow(4,x)*A2[l]/A2[l-1],4))
            if k > 15:
                dp2[l][x] = dp2[l-1][15] + (l+1)*(k -15)
            else:
                dp2[l][x] = dp2[l-1][k] + x


ans = min(2*dp1[0][0],2*dp2[N-1][0]+N)
for i in range(1,N-1):
    ans = min(ans,i+2*(dp1[i][0]+dp2[i-1][0]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
本番中解けず
"""

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

N = int(input())
As = list(map(int, input().split()))

def solve_slow(N, As):
    """位置iを固定してその前後をシミュレート"""
    ans = 1e100
    for i in range(N):
        local_ans = 0
        a = As[i]
        for j in range(i+1, N):
            b = As[j]
            while b < a:
                b *= 4
                local_ans += 2
            a = b

        a = As[i]
        for j in range(i-1, -1, -1):
            b = As[j]
            while b > a:
                b *= -2
                local_ans += 1
            a = b
        ans = min(ans, local_ans)
    return ans

def solve(N, As):
    """実装途中、アイデアなし"""

    table = []
    muls = [0] * N
    divs = [0] * N
    for i in range(1, N):
        prev = As[i-1]
        curr = As[i]
        
        mul = 1
        while prev > curr * mul:
            mul *= 4
        muls[i] = mul

        div = 1
        while curr > prev * div:
            div *= 4
        divs[i] = div

    print(muls)
    print(divs)

    

print(solve_slow(N, As))
#print(solve(N, As))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
log2 = {}
for a in A:
  log2[a] = math.log(a, 2)
# k個目を固定すると仮定したときの操作回数
def process(A, k):
  left = 0
  t = A[k]
  for i in range(k-1, -1, -1):
    a = A[i]
    if a > t:
      if t > 0:
        left += 1
        t = a * (-2)
        log2[-t] = log2[a] + 1
      else:
        l = math.ceil(log2[abs(t)] - log2[a])
        if l % 2 == 0:
          l += 1 # 奇数にする
        left += l
        t = -(a * 2 ** l)
        log2[-t] = log2[a] + l
    else:
      t = a
  right = 0
  t = A[k]
  for i in range(k+1, N):
    a = A[i]
    if t > a:
      l = math.ceil(log2[t] - log2[a])
      if l % 2 == 1:
        l += 1 # 偶数にする
      right += l
      t = a * 2 ** l
      log2[t] = log2[a] + l
    else:
      t = a
  return left + right

if N == 1:
  print(0)
  exit()
# 3分探索
fr = 0
to = N
while to - fr > 2:
  mid1 = fr + ((to - fr)) // 3
  mid2 = fr + ((to - fr) * 2) // 3
  if process(A, mid1) < process(A, mid2):
    to = mid2
  else:
    fr = mid1
print(min(process(A, fr), process(A, fr+1)))