F - Deque Game¶

题意¶

$K$ 個の数列が与えられます。 $i$ 個目の数列 $A_i$ の長さは $N_i$ です。

これらを使って高橋君と青木君がゲームをします。全ての数列が長さ $1$ になるまで、高橋君と青木君が交互に以下の操作を行います。

長さが $2$ 以上の数列を $1$ つ選び、その最初の要素或いは最後の要素を削除する。

高橋君が先に操作を行います。最後に残る $K$ 個の要素の総和を、高橋君は最大化したいと、青木君は最小化したいと考えています。

両者最適に行動するとき、最後に残る $K$ 個の要素の総和を答えてください。

解析¶

在博弈游戏中，我们常常要用到抵消的思想。这一点在 Nim 游戏中的体现就是，必胜方总是可以通过某种操作抵消对方对异或和的影响。而在本题的 Deque 游戏中，当一方取走队首时，另一方总是可以通过取走队尾来“抵消”，使队列中间的元素保持不变。

考虑 $K=1$ 的情况。根据抵消的思想，若 $N_1$ 为奇数，则高橋至少可以使 $\min\left(A_{(N_1+1)/2},\max(A_{(N_1+1)/2-1},A_{(N_1+1)/2+1})\right)$ 剩下。

那高橋君是否能够使剩下的数比 $\min\left(A_{(N_1+1)/2},\max(A_{(N_1+1)/2-1},A_{(N_1+1)/2+1})\right)$ 还要大呢？答案是否定的。青木也可以通过抵消的手段，使当 $N_1$ 为奇数时，最终得数不大于 $\min\left(A_{(N_1+1)/2},\max(A_{(N_1+1)/2-1},A_{(N_1+1)/2+1})\right)$ 。

故，当 $K=1,2\nmid N_1$ 时，答案为

$f(A_1)=\begin{cases} A_1&\text{if }N_1=1\\ \min\left(A_{(N_1+1)/2},\max(A_{(N_1+1)/2-1},A_{(N_1+1)/2+1})\right)&\text{else} \end{cases}$

当 $K>1$ 且 $N_i$ 都是奇数时，答案恰好为 $\sum\limits_{i=1}^Kf(A_i)$ 。因为我们发现，当 $N_i$ 为奇数时，对 $A_i$ 后手取总是比先手取更优。如果高橋取走了 $A_i$ 的首个元素，则青木在接下来，每次高橋操作 $A_i$ 时重复自己的策略，尚且可以保证 $A_i$ 剩下的数仍然为 $f(A_i)$ ；而若青木傻乎乎地抢着取了 $A_i$ 的第一个元素，则高橋就有手段使得 $A_i$ 剩下的数至少为 $\max\left(A_{(N_1+1)/2},\min(A_{(N_1+1)/2-1},A_{(N_1+1)/2+1})\right)\ge f(A_i)$ 了。这样，青木就会避免成为每个 $A_i$ 的先手。于是 $K>1$ 时，每个 $A_i$ 的先手者还是高橋君，每个 $A_i$ 剩下的数还是 $f(A_i)$ 。

如果存在为偶数的 $N_i$ ，则两人会轮流从长度为偶数的 $A_i$ 中删除合适的元素，直到不存在长度为偶数的数列，转化为之前讨论的状态。这一点的证明我并不很清楚，官方题解的英文版似乎也证明得不太详细。

实现¶

#include <bits/stdc++.h>

const int maxn = 2e5 + 19;

int k, cnt;
std::vector<int> a[maxn], d;
long long int ans;

inline int f(const std::vector<int> &a, int l, int r){
    if(l == r) return a[l];
    return std::min(a[(l + r) / 2], std::max(a[(l + r) / 2 - 1], a[(l + r) / 2 + 1]));
}
inline int g(const std::vector<int> &a, int l, int r){
    if(l == r) return a[l];
    return std::max(a[(l + r) / 2], std::min(a[(l + r) / 2 - 1], a[(l + r) / 2 + 1]));
}

int main(){
    std::scanf("%d", &k);
    for(int i = 1, sz; i <= k; ++i){
        std::scanf("%d", &sz); a[i].resize(sz);
        for(int j = 0; j < sz; ++j)
            std::scanf("%d", &a[i][j]);
        if(!(sz & 1)) ++cnt;
    }
    for(int i = 1; i <= k; ++i){
        if(a[i].size() & 1){
            if(cnt & 1) ans += g(a[i], 0, a[i].size() - 1);
            else ans += f(a[i], 0, a[i].size() - 1);
        }else{
            int x, y;
            if(cnt & 1)
                x = g(a[i], 1, a[i].size() - 1), y = g(a[i], 0, a[i].size() - 2);
            else
                x = f(a[i], 1, a[i].size() - 1), y = f(a[i], 0, a[i].size() - 2);
            if(x > y) std::swap(x, y);
            d.push_back(y - x), ans += x;
        }
    }
    std::sort(d.begin(), d.end(), std::greater<int>());
    for(int i = 0; i < (int)d.size(); i += 2)
        ans += d[i];
    std::printf("%lld\n", ans);
    return 0;
}

来源¶

AtCoder Regular Contest 116 F - Deque Game

F - Deque Game¶

题意¶

解析¶

实现¶

来源¶

评论