agc_044e Random Pawn
https://atcoder.jp/contests/agc044/tasks/agc044_e
Tutorial
http://auoj.net/download.php?type=solution-pdf&id=413
https://atcoder.jp/contests/agc044/submissions/14156414
假如卒子移动至 (A_i) 最大的位置,那么一定会直接结束,所以可以断环为链
发现我们需要决策的就是终止点位置的集合,也就是走到哪些位置就直接停止
首先考虑,若所有 (B_i=0) 时的答案.
设 (P_i) 表示从第 (i) 个位置出发的期望收益.
那么对于相邻的两个终止点 (u,v) 有
[egin{cases}
P_u=A_u \
P_v=A_v \
P_i=dfrac {P_{i-1}+P_{i+1}}2 & i in (u,v)
end{cases}
]
这是一个经典模型,可以得到
[P_i = dfrac {(i-u)A_v+(v-i)A_u}{v-u} (i in [u,v])
]
发现这是一个等差数列的形式,可以看作梯形下方的面积.
那么发现,如果要最大化决策点连成的图形下方的面积大小,所选择的就是上凸壳.
那么求 ((i,A_i)) 的上凸壳集合即可.
若 (B_i ot= 0) .
此时 (P_i = dfrac {P_{i-1}+P_{i+1}}2-B_i) .我们想要将其转化为与之前相似的等差数列的形式.
考虑设 (P'_i = P_i-C_i) ,考虑构造数列 (C) 使得上述性质成立.
则有
[egin{cases}
P'_u=A_u-C_u \
P'_v=A_v-C_v \
P'_i = dfrac {P_{i-1}+P_{i+1}}2-B_i -C_i = dfrac {P'_{i-1}+P'_{i+1}}2-B_i-C_i+dfrac {C_{i-1}+C_{i+1}}2 & i in (u,v)
end{cases}
]
那么 (C) 数列需要满足 (B_i = dfrac {C_{i-1}+C_{i+1}}2-C_i) .
可以令 (C_1=C_2=0,C_{i+1}=2(B_i+C_i)-C_{i-1})
那么对于 ((A-C,P'_i)) 求解后,很容易还原出原问题的答案.
复杂度 (O(n))
Code
#include <algorithm>
#include <cstdio>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char nc() {
return getchar();
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x) {
x=0; int f=1,ch=nc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
x*=f;
}
typedef long long ll;
const int maxn=200000+5;
int n; ll a[maxn]; int b[maxn];
ll c[maxn];
int sta[maxn],top;
inline bool invalid(int u,int v,int w) {
return (a[v]-a[u])*(w-v)<=(a[w]-a[v])*(v-u);
}
void rebuild() {
int k=max_element(a+1,a+n+1)-a;
rotate(a+1,a+k,a+n+1);
rotate(b+1,b+k,b+n+1);
a[++n]=a[1],b[n]=b[1];
}
void init() {
for(int i=2;i<n;++i) c[i+1]=2*(b[i]+c[i])-c[i-1];
for(int i=1;i<=n;++i) a[i]-=c[i];
}
double sol() {
rebuild();
init();
for(int i=1;i<=n;++i) {
while(top>1&&invalid(sta[top-1],sta[top],i)) --top;
sta[++top]=i;
}
ll an=0;
for(int i=1;i<top;++i) {
int d=sta[i+1]-sta[i];
an+=a[sta[i]]*(d+1)+a[sta[i+1]]*(d-1);
}
for(int i=1;i<n;++i) an+=c[i]*2;
return an/(2.0*(n-1));
}
int main() {
read(n);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i<=n;++i) read(b[i]);
printf("%.12lf
",sol());
return 0;
}