atcoder#AGC044E. [AGC044E] Random Pawn

[AGC044E] Random Pawn

配点 : 13001300

問題文

あなたの目的は、これからプレイするゲームでの利得の期待値を最大化することです。 ゲームを開始すると、ポーン (チェスの駒) が {1,2,,N}\{1,2,\dots, N\} から等確率に選ばれた位置 pp に置かれます。これらの NN 個の位置 1,2,,N1, 2, \dots, N は円周上に時計回りに並び、位置 11 の両隣は位置 N,2N, 2 です。

ゲームはターン制で進行します。各ターンでは、ゲームを終えて ApA_p ドル (pp はその時点でのポーンの位置) を得るか、BpB_p ドルを支払ってゲームを続けるかを選べます。 ゲームを続ける場合、ポーンは自身と隣接する 22 つの位置 p1p-1, p+1p+1 のいずれかに等確率で移されます (位置 00 は位置 NN と、位置 N+1N+1 は位置 11 とみなします)。

最適な戦略の期待利得は何ドルでしょうか。

注記: 「最適な戦略の期待利得」は、ゲームが 有限の ターン数で終わるような戦略における期待利得の上限と定義されます。

制約

  • 2N200,0002 \le N \le 200,000
  • 0Ap10120 \le A_p \le 10^{12} (p=1,,Np = 1,\ldots, N)
  • 0Bp1000 \le B_p \le 100 (p=1,,Np = 1, \ldots, N)
  • 入力中のすべての値は整数である。

入力

入力は標準入力から以下の形式で与えられる。

NN

A1A_1 A2A_2 \cdots ANA_N

B1B_1 B2B_2 \cdots BNB_N

出力

最適な戦略の期待利得を 11 個の実数として出力せよ。

出力された値は、絶対誤差または相対誤差が 101010^{-10} を超えなければ正解とみなされる。

5
4 2 6 3 5
1 1 1 1 1
4.700000000000
4
100 0 100 0
0 100 0 100
50.000000000000
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
7047.142857142857
10
470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951
26 83 30 59 100 88 84 91 54 61
815899161079.400024414062