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: Runtime Error

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
        if(end[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)

            left = seg_left.query(0,ind)
            right = seg_right.query(ind+1,n+1)
            if(left!=0):
                order.append(left)
            if(right!=0):
                order.append(right)
            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: Runtime Error

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])
#        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: Runtime Error

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: Runtime Error

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

import sys
sys.setrecursionlimit(10**7)

def getMoney(now, money):
    if money >= (a[(now+1)%n]+a[(now-1)%n])/2 - b[now]: return money
    x = getMoney((now+1)%n, a[(now+1)%n] - b[now])
    y = getMoney((now-1)%n, a[(now-1)%n] - b[now])
    return (x+y)/2

anss = []
for i in range(n):
    ans = getMoney(i,a[i])
    anss.append(ans)
ans = sum(anss)/n
print(ans)

Submission status: Runtime Error

Solution code:
わからん！w

Submission status: Runtime Error

Solution code:
def update(i, n, a_list, b_list, prev_g_list):
    next_expectation = 0.5 * (prev_g_list[i - 1] + prev_g_list[(i + 1) % n]) - b_list[i]
    return a_list[i] if a_list[i] >= next_expectation else next_expectation

def solve(n, a_list, b_list):
    prev_g_list = [max(a_list)] * n
    prev_sum = sum(prev_g_list)
    while True:
        tmp_new_g_list = [update(i, n, a_list, b_list, prev_g_list) for i in range(n)]
        new_g_list = [a_list[i] if abs(item - a_list[i]) < 1e-2 else item for (i, item) in enumerate(tmp_new_g_list)]
        new_sum = sum(new_g_list)

        if abs(new_sum / prev_sum - 1.0) < 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().strip().split()]
    b_list = [int(s) for s in input().strip().split()]
    res = solve(n, a_list, b_list)
    print(res)

Submission status: Runtime Error

Solution code:
def update(i, n, a_list, b_list, prev_g_list):
    next_expectation = 0.5 * (prev_g_list[i - 1] + prev_g_list[(i + 1) % n]) - b_list[i]
    return a_list[i] if a_list[i] >= next_expectation else next_expectation

def solve(n, a_list, b_list):
    prev_g_list = [max(a_list)] * n
    prev_sum = sum(prev_g_list)
    while True:
        tmp_new_g_list = [update(i, n, a_list, b_list, prev_g_list) for i in range(n)]
        new_g_list = [a_list[i] if abs(item - a_list[i]) < 1e-2 else item for (i, item) in enumerate(tmp_new_g_list)]
        new_sum = sum(new_g_list)

        if abs(new_sum / prev_sum - 1) < 1e-11:
            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().strip().split()]
    b_list = [int(s) for s in input().strip().split()]
    res = solve(n, a_list, b_list)
    print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf



def getMoney(now, money):
    if money >= (a[(now+1)%n]+a[(now-1)%n])/2 - b[now]: return money
    x = getMoney((now+1)%n, a[(now+1)%n] - b[now])
    y = getMoney((now-1)%n, a[(now-1)%n] - b[now])
    return (x+y)/2

n = int(input())
a = iarr()
b = iarr()


anss = []
for i in range(n):
    ans = getMoney(i,a[i])
    anss.append(ans)
ans = sum(anss)/n
print(ans)

Submission status: Runtime Error

Solution code:
sfgsfh