/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1300 点
問題文
あなたの目的は、これからプレイするゲームでの利得の期待値を最大化することです。 ゲームを開始すると、ポーン (チェスの駒) が \{1,2,\dots, N\} から等確率に選ばれた位置 p に置かれます。これらの N 個の位置 1, 2, \dots, N は円周上に時計回りに並び、位置 1 の両隣は位置 N, 2 です。
ゲームはターン制で進行します。各ターンでは、ゲームを終えて A_p ドル (p はその時点でのポーンの位置) を得るか、B_p ドルを支払ってゲームを続けるかを選べます。 ゲームを続ける場合、ポーンは自身と隣接する 2 つの位置 p-1, p+1 のいずれかに等確率で移されます (位置 0 は位置 N と、位置 N+1 は位置 1 とみなします)。
最適な戦略の期待利得は何ドルでしょうか。
注記: 「最適な戦略の期待利得」は、ゲームが 有限の ターン数で終わるような戦略における期待利得の上限と定義されます。
制約
- 2 \le N \le 200,000
- 0 \le A_p \le 10^{12} (p = 1,\ldots, N)
- 0 \le B_p \le 100 (p = 1, \ldots, N)
- 入力中のすべての値は整数である。
入力
入力は標準入力から以下の形式で与えられる。
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
出力
最適な戦略の期待利得を 1 個の実数として出力せよ。
出力された値は、絶対誤差または相対誤差が 10^{-10} を超えなければ正解とみなされる。
入力例 1
5 4 2 6 3 5 1 1 1 1 1
出力例 1
4.700000000000
入力例 2
4 100 0 100 0 0 100 0 100
出力例 2
50.000000000000
入力例 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
出力例 3
7047.142857142857
入力例 4
10 470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951 26 83 30 59 100 88 84 91 54 61
出力例 4
815899161079.400024414062
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