AT_agc044_e.[AGC044E] Random Pawn
NOI/NOI+/CTSC
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
你的目标是在接下来要进行的游戏中最大化期望收益。当游戏开始时，棋子（象棋棋子）会以等概率被放置在 $ {1,2,\dots,N} $ 中的某个位置 $ p $。这 $ N $ 个位置 $ 1,2,\dots,N $ 顺时针排列在圆周上，位置 $ 1 $ 的相邻位置是 $ N $ 和 $ 2 $。
游戏以回合制进行。在每一回合，你可以选择结束游戏并获得 $ A_p $ 美元（$ p $ 是当前棋子的位置），或者支付 $ B_p $ 美元继续游戏。如果选择继续游戏，棋子会以等概率移动到相邻的两个位置 $ p-1 $ 或 $ p+1 $（位置 $ 0 $ 视为位置 $ N $，位置 $ N+1 $ 视为位置 $ 1 $）。
最优策略下的期望收益是多少美元？
注意：“最优策略下的期望收益”定义为在保证游戏在有限回合内结束的策略下，期望收益的上界。
输入格式
输入从标准输入中按以下格式给出。
$ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_N $
输出格式
请输出最优策略下的期望收益，输出一个实数。
只要输出的值与标准答案的绝对误差或相对误差不超过 $ 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
说明/提示
限制
- $ 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 $）
- 输入中的所有数值均为整数。
由 ChatGPT 4.1 翻译
输入解题思路，AI测评打分。不知道怎么写?