题解：AT_agc056_d [AGC056D] Subset Sum Game

· · 题解

Sol

假如 Bob 先手，他的目的就是让 Alice 拿到的和尽可能小或者尽可能大。

假如尽可能小，先给序列升序排序，此时 Alice 至多拿到 A_1,A_3,\dots, A_{n-1}，如果这个值比 L 小显然可以，那么这个值比 L 大必然不行吗？也有可能大于 R 然后 Alice 无法选到 [L,R] 之间？然而如果这个值大于 R，那么 A_2,A_4,\dots,A_n 显然也大于 R，Bob 还是能赢。尽可能大同理。

假如奇数位和 \ge L 且偶数位和 \le R Alice 必赢吗？是的。将原序列两两相邻捆绑，Bob 选了其中一个，Alice 就选另一个即可。

现在就相当于是 Alice 先走一步然后开始 Bob 先手。这样的话假如序列符合条件那么显然第一步随便走然后遵循上述策略即可。

然而原序列不符合上述条件时，并不一定不行。

不妨先枚举 Alice 第一步选的 x，然后 L,R 自减 x 变为 Bob 先手子问题，那么假如剩下的序列中存在一个长 n-2 的子序列符合条件，就可以直接遵循上述策略做，剩下那个多余的空留给 Bob 去填即可，填完后变为 Alice 先手接着做就完了。

但假如不存在这么一个子序列就一定不符合条件吗？也就是说对于每个 n-1 长的序列，其删去一点 x 后所有 n-2 长度的子序列，要么奇数位和小于 L-x 要么偶数位和大于 R-x，前者删的点在一个后缀，后者删的点在一个前缀。并且由于删除点移动一位，只会变化奇数位和或偶数位和中一个，因此必然存在一个位置使得剩下的 n-2 长度序列奇数位和小于 L-x 且偶数位和大于 R-x。而对于一个奇数位和小于 L 且偶数位和大于 R 的 Alice 先手序列，可以归纳证明其所有 n-2 长度的子序列必然满足奇数位和小于 L 或偶数位和大于 R 至少其一，于是可以递归为子问题，直到 n=2，显然 Bob 必胜。

所以这个条件是充要的。于是可以简单 O(n^2) 模拟，就做完了。

Code

const int N=5005;

int n;
ll l,r,a[N],s1[N],s2[N];

inline void Main(){
    cin>>n>>l>>r;
    rep(i,1,n)cin>>a[i];sort(a+1,a+1+n);
    s1[1]=a[1];
    rep(i,2,n)s1[i]=s1[i-1],s2[i]=s2[i-1],(i&1?s1:s2)[i]+=a[i];
    rep(i,1,n)repl(j,1,i)if(s1[j-1]+s2[i-1]-s2[j]+s1[n]-s1[i]>=l-a[i]&&s2[j-1]+s1[i-1]-s1[j]+s2[n]-s2[i]<=r-a[i])return put("Alice"),void();
    rep(i,1,n)repl(j,1,i)if(s1[j-1]+s2[i-1]-s2[j]+s1[n]-s1[i]>=l-a[j]&&s2[j-1]+s1[i-1]-s1[j]+s2[n]-s2[i]<=r-a[j])return put("Alice"),void();
    put("Bob");
}