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()))
tmp = 0
REP = max(30, 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
    for i in range(1, N+1):
        val = max(float(A[i]), (float(A[i-1]+A[i+1])/2 - B[i]))
        tmp += float(val)
        A[i] = float(val)
    A[0] = float(A[N])
    A[N+1] = float(A[1])
print(float(tmp/N))

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
tmp = 0
REP = max(50, 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: Wrong Answer

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

REP = 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: Wrong Answer

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]
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 [-1,1]:
            j += ind
            if(0<j<n)&(end[j] == 1):
                order.append(j)

# 終了すべきポイントがわかったので期待値合計を計算
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: Wrong Answer

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
for ai,ind in order:
    if(ind==0):
        continue

    ex,div = calc_ex(ind)
    if(ai*div < ex):
        end[ind] = 0
        seg_left.update(ind,0)
        seg_right.update(ind,n)

# 終了すべきポイントがわかったので期待値合計を計算
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: Wrong Answer

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(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] * (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('{:.100f}'.format(ans_num/(lcm*n)))

Submission status: Wrong Answer

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(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] * (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('{:.10f}'.format(ans_num/(lcm*n)))

Submission status: Wrong Answer

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(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] * (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: 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]/n
    else:
        ex,div = calc_ex(ind)
        ans += ex/(div*n)

print(ans)