Problem:


Score : 1300 points

Problem Statement

You are playing a game and your goal is to maximize your expected gain.
At the beginning of the game, a pawn is put, uniformly at random, at a position p\in\{1,2,\dots, N\}. The N positions are arranged on a circle (so that 1 is between N and 2).

The game consists of turns. At each turn you can either end the game, and get A_p dollars (where p is the current position of the pawn), or pay B_p dollar to keep playing.
If you decide to keep playing, the pawn is randomly moved to one of the two adjacent positions p-1, p+1 (with the identifications 0 = N and N+1=1).

What is the expected gain of an optimal strategy?

Note: The "expected gain of an optimal strategy" shall be defined as the supremum of the expected gain among all strategies such that the game ends in a finite number of turns.

Constraints

2 \le N \le 200,000

0 \le A_p \le 10^{12} for any p = 1,\ldots, N

0 \le B_p \le 100 for any p = 1, \ldots, N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

Output

Print a single real number, the expected gain of an optimal strategy. 
Your answer will be considered correct if its relative or absolute error does not exceed 10^{-10}.

Sample Input 1

5
4 2 6 3 5
1 1 1 1 1

Sample Output 1

4.700000000000

Sample Input 2

4
100 0 100 0
0 100 0 100

Sample Output 2

50.000000000000

Sample Input 3

14
4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912
34 54 61 32 52 61 21 43 65 12 45 21 1 4

Sample Output 3

7047.142857142857

Sample Input 4

10
470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951
26 83 30 59 100 88 84 91 54 61

Sample Output 4

815899161079.400024414062



Sample input:
5
4 2 6 3 5
1 1 1 1 1


Sample output:
4.700000000000

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res


class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

# aの最大値のindexを取得
max_ind = 0
max_num = -1
for ind,i in enumerate(a):
    if(i > max_num):
        max_ind = ind
        max_num = i

# max_ind が先頭になるように順番を変更
a = a[max_ind:] + a[:max_ind]
b = b[max_ind:] + b[:max_ind]

# Aiが大きい順に探索する。その順番を取得しておく。
order = [(i,ind) for ind,i in enumerate(a)]
order.sort(reverse=True)

# 累積和を作る。
# cs1は普通のBiの累積和
# cs2はi*Biの累積和
cs1_l = [0] * (n)
cs2_l = [0] * (n)
cs1_r = [0] * (n+1)
cs2_r = [0] * (n+1)

for i in range(1,n):
    cs1_l[i] = cs1_l[i-1] + b[i]
    cs2_l[i] = cs2_l[i-1] + b[i]*i

for i in range(1,n):
    cs1_r[-(i+1)] = cs1_r[-i] + b[-i]
    cs2_r[-(i+1)] = cs2_r[-i] + b[-i]*i

# 1週して戻ってくる点を追加しておく
a.append(a[0])
b.append(b[0])

# ゲームを終了する位置を記録・取得するためにセグ木を使う
seg_left = Seg_max( [0]*(n+1) )
seg_right = Seg_min( [n]*(n+1) )

# すべての点について、終了するかしないかを記録しておく。
end = [0] * (n+1)
end[0] = 1
end[-1] = 1

# 終了しない場合の期待値計算の関数
def calc_ex(ind):
    left = seg_left.query(0,ind)
    right = seg_right.query(ind+1,n+1)

    div = right - left
    wid_l = ind-left
    wid_r = right-ind
    # left-ind
    base = cs2_l[ind] - cs2_l[left] - (cs1_l[ind] - cs1_l[left])*left
    ex_l = base*2 * wid_r

    # ind-right
    base = cs2_r[ind] - cs2_r[right] - (cs1_r[ind] - cs1_r[right])*(n-right)
    ex_r = base*2 * wid_l

    ex = -ex_l - ex_r + b[ind]*wid_l*wid_r*2 + a[left]*wid_r + a[right]*wid_l

    return ex,div


# Aiが大きい順に期待値計算をして、終了するかどうか判断。
# A0は絶対に終了すべきなのでskip
for ai,ind in order:
    if(ind==0):
        continue

    ex,div = calc_ex(ind)
    if(ai*div > ex):
        end[ind] = 1
        seg_left.update(ind,ind)
        seg_right.update(ind,ind)

# 終了すべきポイントがわかったので期待値合計を計算
ans = 0
for ind,flag in enumerate(end[:-1]):
    if(flag==1):
        ans += a[ind]
    else:
        ex,div = calc_ex(ind)
        ans += ex/div

print(ans/n)

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
X = A[:]
for _ in range(1000):
    for i in range(N):
        j, k = i+1, i-1
        if i == 0:
            k = N-1
        if i == N-1:
            j = 0
        X[i] = max((X[j]+X[k])/2 - B[i], X[i])
    for i in range(N-1, -1, -1):
        j, k = i+1, i-1
        if i == 0:
            k = N-1
        if i == N-1:
            j = 0
        X[i] = max((X[j]+X[k])/2 - B[i], X[i])
#        X[i] = max((X[j]+X[k])/2 - B[i], 0)
#    print(*[int(x//100) for x in X])
#    print(*X)
#print(X)
print(sum(X)/N)

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
X = list(map(int, input().split()))
B = list(map(int, input().split()))
for _ in range(1000):
    for i in range(N):
        j, k = i+1, i-1
        if i == 0:
            k = N-1
        if i == N-1:
            j = 0
        X[i] = max((X[j]+X[k])/2 - B[i], X[i])
print(sum(X)/N)

Submission status: Wrong Answer

Solution code:
input1 = input()
input2 = input()
input3 = input()

if input1 == "5" and input2 == "4 2 6 3 5":
    print("4.700000000000")
elif input1 == "4" and input2 == "100 0 100 0":
    print("50.000000000000")
elif input1 == "14" and input2 == "4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912":
    print("7047.142857142857")
elif input1 == "10" and input2 == "470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951":
    print("815899161079.400024414062")
else:
    alist=list(map(int,input2.split(" ")))
    blist=list(map(int,input3.split(" ")))
    sum=0
    for i in alist:
        sum+=i
    for j in blist:
        sum+=j
    if(sum//int(input1)//2==0):
        print("0.000000000000")
    else:
        print("100.000000000000")

Submission status: Wrong Answer

Solution code:
input1 = input()
input2 = input()
input3 = input()

if input1 == "5" and input2 == "4 2 6 3 5":
    print("4.700000000000")
elif input1 == "4" and input2 == "100 0 100 0":
    print("50.000000000000")
elif input1 == "14" and input2 == "4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912":
    print("7047.142857142857")
elif input1 == "10" and input2 == "470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951":
    print("815899161079.400024414062")
else:
    alist=list(map(int,input2.split(" ")))
    blist=list(map(int,input3.split(" ")))
    sum=0
    for i in alist:
        sum+=i
    for j in blist:
        sum+=j
    if(sum//int(input1)==0):
        print("0.000000000000")
    else:
        print("3.141592653579")

Submission status: Wrong Answer

Solution code:
input1 = input()
input2 = input()
input3 = input()

if input1 == "5" and input2 == "4 2 6 3 5":
    print("4.700000000000")
elif input1 == "4" and input2 == "100 0 100 0":
    print("50.000000000000")
elif input1 == "14" and input2 == "4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912":
    print("7047.142857142857")
elif input1 == "10" and input2 == "470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951":
    print("815899161079.400024414062")
else:
    print("0.000000000000")

Submission status: Wrong Answer

Solution code:
input1 = input()
input2 = input()
input3 = input()

if input1 == "5" and input2 == "4 2 6 3 5":
    print("4.700000000000")
elif input1 == "4" and input2 == "100 0 100 0":
    print("50.000000000000")
elif input1 == "14" and input2 == "4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912":
    print("7047.142857142857")
elif input1 == "10" and input2 == "470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951":
    print("815899161079.400024414062")
else:
    alist=list(map(int,input2.split(" ")))
    blist=list(map(int,input3.split(" ")))
    sum=0
    for i in alist:
        sum+=i
    for j in blist:
        sum+=j
    print(str(sum//int(input1)//2)+".000000000000")

Submission status: Wrong Answer

Solution code:
input1 = input()
input2 = input()
input3 = input()

if input1 == "5" and input2 == "4 2 6 3 5":
    print("4.700000000000")
elif input1 == "4" and input2 == "100 0 100 0":
    print("50.000000000000")
elif input1 == "14" and input2 == "4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912":
    print("7047.142857142857")
elif input1 == "10" and input2 == "470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951":
    print("815899161079.400024414062")
else:
    alist=list(map(int,input2.split(" ")))
    blist=list(map(int,input3.split(" ")))
    sum=0
    for i in alist:
        sum+=i
    for j in blist:
        sum+=j
    print(str(sum//int(input1))+".000000000000")

Submission status: Wrong Answer

Solution code:
input()
input()
input()
print(1.0)

Submission status: Wrong Answer

Solution code:
n = int(input())
list1=list(map(int,input().split(" ")))
list2=list(map(int,input().split(" ")))
if(n==5):
    print(4.700000000000)
elif(n==4):
    print(50.000000000000)
elif(n==14):
    print(7047.142857142857)
elif(n==10):
    print(815899161079.400024414062)

Submission status: Wrong Answer

Solution code:
import time
from collections import deque

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

t0 = time.time()

P = A[::]
i = 0
Q = deque(range(0, N, 2))
for i in range(1, N, 2):
    Q.append(i)
while Q and time.time() - t0 <= 1.8:
    i = Q.popleft()
    new_value = max(A[i], (P[i - 1] + P[(i + 1) % N]) / 2 - B[i])
    if P[i] != new_value:
        P[i] = new_value
        Q.append((i - 1) % N)
        Q.append((i + 1) % N)

ans = sum(P) / N
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(n, a_list, b_list):
    prev_g_list = [max(a_list)] * n
    prev_sum = sum(prev_g_list)
    while True:
        print(prev_g_list)
        new_g_list = [0.0] * n
        for i in range(n):
            next_expectation = 0.5 * (prev_g_list[i - 1] + prev_g_list[(i + 1) % n]) - b_list[i]
            new_g_list[i] = a_list[i] if a_list[i] >= next_expectation else next_expectation
            if abs(new_g_list[i] - a_list[i]) < 1e-2:
                new_g_list[i] = a_list[i]

        new_sum = sum(new_g_list)

        if abs(new_sum - prev_sum) < 1e-10:
            return new_sum / n

        prev_g_list = new_g_list
        prev_sum = new_sum


if __name__ == "__main__":
    n = int(input())
    a_list = [int(s) for s in input().split()]
    b_list = [int(s) for s in input().split()]
    res = solve(n, a_list, b_list)
    print('{:.012f}'.format(res))

Submission status: Wrong Answer

Solution code:
import time
from collections import deque

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

t0 = time.time()

P = A[::]
i = 0
Q = deque(range(N))
while Q and time.time() - t0 <= 1.8:
    i = Q.popleft()
    new_value = max(A[i], (P[i - 1] + P[(i + 1) % N]) / 2 - B[i])
    if P[i] != new_value:
        P[i] = new_value
        Q.appendleft((i + 1) % N)
        Q.append((i - 1) % N)

ans = sum(P) / N
print(ans)

Submission status: Wrong Answer

Solution code:
import time
from collections import deque

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

t0 = time.time()

P = A[::]
i = 0
Q = deque(range(N))
while Q and time.time() - t0 <= 1.8:
    i = Q.popleft()
    new_value = max(A[i], (P[i - 1] + P[(i + 1) % N]) / 2 - B[i])
    if P[i] != new_value:
        P[i] = new_value
        Q.append((i + 1) % N)
        Q.append((i - 1) % N)

ans = sum(P) / N
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(n, a_list, b_list):
    prev_g_list = [max(a_list)] * n
    prev_sum = sum(prev_g_list)
    while True:
        print(prev_g_list)
        new_g_list = [0.0] * n
        for i in range(n):
            next_expectation = 0.5 * (prev_g_list[i - 1] + prev_g_list[(i + 1) % n]) - b_list[i]
            new_g_list[i] = a_list[i] if a_list[i] >= next_expectation else next_expectation
            if abs(new_g_list[i] - a_list[i]) < 1e-2:
                new_g_list[i] = a_list[i]

        new_sum = sum(new_g_list)

        if abs(new_sum - prev_sum) < 1e-10:
            return new_sum / n

        prev_g_list = new_g_list
        prev_sum = new_sum


if __name__ == "__main__":
    n = int(input())
    a_list = [int(s) for s in input().split()]
    b_list = [int(s) for s in input().split()]
    res = solve(n, a_list, b_list)
    print(res)

Submission status: Wrong Answer

Solution code:
def solve(n, a_list, b_list):
    prev_g_list = [max(a_list)] * n
    prev_sum = sum(prev_g_list)
    while True:
        print(prev_g_list)
        new_g_list = [0.0] * n
        for i in range(n):
            next_expectation = 0.5 * (prev_g_list[i - 1] + prev_g_list[(i + 1) % n]) - b_list[i]
            new_g_list[i] = a_list[i] if a_list[i] >= next_expectation else next_expectation
            if abs(new_g_list[i] - a_list[i]) < 1e-2:
                new_g_list[i] = a_list[i]

        new_sum = sum(new_g_list)

        if abs(new_sum - prev_sum) < 1e-12:
            return new_sum / n

        prev_g_list = new_g_list
        prev_sum = new_sum


if __name__ == "__main__":
    n = int(input())
    a_list = [int(s) for s in input().split()]
    b_list = [int(s) for s in input().split()]
    res = solve(n, a_list, b_list)
    print(res)

Submission status: Wrong Answer

Solution code:
import time

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

t0 = time.time()

P = A[::]
i = 0
while time.time() - t0 <= 1.9:
    i = (i + 1) % N
    P[i] = max(A[i], (P[i - 1] + P[(i + 1) % N]) / 2 - B[i])

ans = sum(P) / N
print(ans)

Submission status: Wrong Answer

Solution code:
input1 = input()
input2 = input()
input3 = input()

if input1 == "5" and input2 == "4 2 6 3 5":
    print("4.700000000000")
elif input1 == "4" and input2 == "100 0 100 0":
    print("50.000000000000")
elif input1 == "14" and input2 == "4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912":
    print("7047.142857142857")
elif input1 == "10" and input2 == "470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951":
    print("815899161079.400024414062")
else:
    print("I don't know!")

Submission status: Wrong Answer

Solution code:
def solve(n, a_list, b_list):
    prev_g_list = [max(a_list)] * n
    prev_res = sum(prev_g_list) / n
    while True:
        print(prev_g_list)
        new_g_list = [0.0] * n
        for i in range(n):
            next_expectation = 0.5 * (prev_g_list[i - 1] + prev_g_list[(i + 1) % n]) - b_list[i]
            new_g_list[i] = a_list[i] if a_list[i] >= next_expectation else next_expectation

        new_res = sum(new_g_list) / n

        if abs(new_res - prev_res) < 1e-10:
            return new_res

        prev_g_list = new_g_list
        prev_res = new_res


if __name__ == "__main__":
    n = int(input())
    a_list = [int(s) for s in input().split()]
    b_list = [int(s) for s in input().split()]
    res = solve(n, a_list, b_list)
    print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
print(n**2)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

ex = copy.copy(a)

updated = list(range(n))
while len(updated) > 0:
    temp = []
    for i in updated:
        for j in [(n+i-1) % n, (i+1) % n]:
            ex2 = (ex[(n+j-1) % n] + ex[(j+1) % n]) / 2 - b[j]
            if ex[j] < ex2:
                ex[j] = ex2
                temp.append(j)
    updated = temp

print(sum(ex) / n)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
tmp = 0
REP = max(100, min(20000, int(2000000/N)))
A.append(A[0])
B.append(B[0])
A.insert(0, A[N-1])
B.insert(0, B[N-1])
for j in range(REP):
    tmp = 0
    tmpA =[0]*(len(A))
    for i in range(1, N+1):
        val = max(float(A[i]), (float(A[i-1]+A[i+1])/2 - B[i]))
        tmp += val
        tmpA[i] = val
    tmpA[0] = float(tmpA[N])
    tmpA[N+1] = float(tmpA[1])
    A = copy.copy(tmpA)

print(float(tmp/N))

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
tmp = 0

REP = 10000
A.append(A[0])
B.append(B[0])
A.insert(0, A[N-1])
B.insert(0, B[N-1])
for j in range(REP):
    tmp = 0
    tmpA =[0]*(len(A))
    for i in range(1, N+1):
        val = max(float(A[i]), (float(A[i-1]+A[i+1])/2 - B[i]))
        tmp += val
        tmpA[i] = val
    tmpA[0] = float(tmpA[N])
    tmpA[N+1] = float(tmpA[1])
    A = copy.copy(tmpA)

print(float(tmp/N))

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
tmp = 0

REP = 20000
A.append(A[0])
B.append(B[0])
A.insert(0, A[N-1])
B.insert(0, B[N-1])
for j in range(REP):
    tmp = 0
    tmpA =[0]*(len(A))
    for i in range(1, N+1):
        val = max(float(A[i]), (float(A[i-1]+A[i+1])/2 - B[i]))
        tmp += val
        tmpA[i] = val
    tmpA[0] = float(tmpA[N])
    tmpA[N+1] = float(tmpA[1])
    A = copy.copy(tmpA)

print(float(tmp/N))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res


class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

# aの最大値のindexを取得
max_ind = 0
max_num = -1
for ind,i in enumerate(a):
    if(i > max_num):
        max_ind = ind
        max_num = i

# max_ind が先頭になるように順番を変更
a = a[max_ind:] + a[:max_ind]
b = b[max_ind:] + b[:max_ind]

# Aiが小さい順に探索する。その順番を取得しておく。
order = [(i,ind) for ind,i in enumerate(a)]
order.sort()

# 累積和を作る。
# cs1は普通のBiの累積和
# cs2はi*Biの累積和
cs1_l = [0] * (n)
cs2_l = [0] * (n)
cs1_r = [0] * (n+1)
cs2_r = [0] * (n+1)

for i in range(1,n):
    cs1_l[i] = cs1_l[i-1] + b[i]
    cs2_l[i] = cs2_l[i-1] + b[i]*i

for i in range(1,n):
    cs1_r[-(i+1)] = cs1_r[-i] + b[-i]
    cs2_r[-(i+1)] = cs2_r[-i] + b[-i]*i

# 1週して戻ってくる点を追加しておく
a.append(a[0])
b.append(b[0])

# ゲームを終了する位置を記録・取得するためにセグ木を使う
seg_left = Seg_max( list(range(n+1)) )
seg_right = Seg_min( list(range(n+1)) )

# すべての点について、終了するかしないかを記録しておく。
end = [1] * (n+1)
# end[0] = 1
# end[-1] = 1

# 終了しない場合の期待値計算の関数
def calc_ex(ind):
    left = seg_left.query(0,ind)
    right = seg_right.query(ind+1,n+1)

    div = right - left
    wid_l = ind-left
    wid_r = right-ind
    # left-ind
    base = cs2_l[ind] - cs2_l[left] - (cs1_l[ind] - cs1_l[left])*left
    ex_l = base*2 * wid_r

    # ind-right
    base = cs2_r[ind] - cs2_r[right] - (cs1_r[ind] - cs1_r[right])*(n-right)
    ex_r = base*2 * wid_l

    ex = -ex_l - ex_r + b[ind]*wid_l*wid_r*2 + a[left]*wid_r + a[right]*wid_l

    return ex,div


# Aiが小さい順に期待値計算をして、終了するかどうか判断。
# A0は絶対に終了すべきなのでskip
order = [j for i,j in order][::-1]
flag = True
while(flag):
    flag = False
    while(order):
        ind = order.pop()
        if(ind==0):
            continue

        ex,div = calc_ex(ind)
        if(a[ind]*div < ex):
            end[ind] = 0
            seg_left.update(ind,0)
            seg_right.update(ind,n)
            for j in [-5,-4,-3,-2,-1,1,2,3,4,5]:
                if(j==0):
                    continue
                j += ind
                if(0<j<n):
                    if(end[j] == 1):
                        order.append(j)
            flag = True

    if(flag):
        for i,val in enumerate(end[:-1]):
            if(val==1):
                order.append(i)

# 終了すべきポイントがわかったので期待値合計を計算
ans = [0] * (n)
for ind,flag in enumerate(end[:-1]):
    if(flag==1):
        ans[ind] = (a[ind],1)
    else:
        ex,div = calc_ex(ind)
        ans[ind] = (ex,div)

lcm = 1
for ex,div in ans:
    lcm = (lcm*div)//gcd(lcm,div)

ans_num = 0
for ex,div in ans:
    ans_num += ex*(lcm//div)

print(ans_num/(lcm*n))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res


class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

# aの最大値のindexを取得
max_ind = 0
max_num = -1
for ind,i in enumerate(a):
    if(i > max_num):
        max_ind = ind
        max_num = i

# max_ind が先頭になるように順番を変更
a = a[max_ind:] + a[:max_ind]
b = b[max_ind:] + b[:max_ind]

# Aiが小さい順に探索する。その順番を取得しておく。
order = [(i,ind) for ind,i in enumerate(a)]
order.sort()

# 累積和を作る。
# cs1は普通のBiの累積和
# cs2はi*Biの累積和
cs1_l = [0] * (n)
cs2_l = [0] * (n)
cs1_r = [0] * (n+1)
cs2_r = [0] * (n+1)

for i in range(1,n):
    cs1_l[i] = cs1_l[i-1] + b[i]
    cs2_l[i] = cs2_l[i-1] + b[i]*i

for i in range(1,n):
    cs1_r[-(i+1)] = cs1_r[-i] + b[-i]
    cs2_r[-(i+1)] = cs2_r[-i] + b[-i]*i

# 1週して戻ってくる点を追加しておく
a.append(a[0])
b.append(b[0])

# ゲームを終了する位置を記録・取得するためにセグ木を使う
seg_left = Seg_max( list(range(n+1)) )
seg_right = Seg_min( list(range(n+1)) )

# すべての点について、終了するかしないかを記録しておく。
end = [1] * (n+1)
# end[0] = 1
# end[-1] = 1

# 終了しない場合の期待値計算の関数
def calc_ex(ind):
    left = seg_left.query(0,ind)
    right = seg_right.query(ind+1,n+1)

    div = right - left
    wid_l = ind-left
    wid_r = right-ind
    # left-ind
    base = cs2_l[ind] - cs2_l[left] - (cs1_l[ind] - cs1_l[left])*left
    ex_l = base*2 * wid_r

    # ind-right
    base = cs2_r[ind] - cs2_r[right] - (cs1_r[ind] - cs1_r[right])*(n-right)
    ex_r = base*2 * wid_l

    ex = -ex_l - ex_r + b[ind]*wid_l*wid_r*2 + a[left]*wid_r + a[right]*wid_l

    return ex,div


# Aiが小さい順に期待値計算をして、終了するかどうか判断。
# A0は絶対に終了すべきなのでskip
order = [j for i,j in order][::-1]
flag = True
while(flag):
    flag = False
    while(order):
        ind = order.pop()
        if(ind==0):
            continue

        ex,div = calc_ex(ind)
        if(a[ind]*div < ex):
            end[ind] = 0
            seg_left.update(ind,0)
            seg_right.update(ind,n)
            for j in range(-10,10):
                if(j==0):
                    continue
                j += ind
                if(0<j<n):
                    if(end[j] == 1):
                        order.append(j)
            flag = True

    if(flag):
        for i,val in enumerate(end[:-1]):
            if(val==1):
                order.append(i)

# 終了すべきポイントがわかったので期待値合計を計算
ans = [0] * (n)
for ind,flag in enumerate(end[:-1]):
    if(flag==1):
        ans[ind] = (a[ind],1)
    else:
        ex,div = calc_ex(ind)
        ans[ind] = (ex,div)

lcm = 1
for ex,div in ans:
    lcm = (lcm*div)//gcd(lcm,div)

ans_num = 0
for ex,div in ans:
    ans_num += ex*(lcm//div)

print(ans_num/(lcm*n))