很强的博弈 + 性质题。下文令 A 为 Takahashi,B 为 Aoki。
发现单独考虑一个序列 \(a_1,a_2,...,a_n\):
- 若 \(n \bmod 2 = 0\):
- 若 A 为先手,答案为 \(\max(a_{\frac{n}{2}}, a_{\frac{n}{2} + 1})\);
- 若 B 为先手,答案为 \(\min(a_{\frac{n}{2}}, a_{\frac{n}{2} + 1})\)(由于 \(\min\) 和 \(\max\) 的对称性)。
- 双方都是成为先手比成为后手优。
- 若 \(n \bmod 2 = 1\):
- 若 A 为先手,答案为 \(\min(a_{\frac{n+1}{2}}, \max(a_{\frac{n+1}{2} - 1}, a_{\frac{n+1}{2} + 1}))\);
- 若 B 为先手,答案为 \(\max(a_{\frac{n+1}{2}}, \min(a_{\frac{n+1}{2} - 1}, a_{\frac{n+1}{2} + 1}))\);
- 双方都是成为后手比成为先手优。
相同的结论在 CF794E 也出现过。这是容易归纳证明的,故证明略。
考虑如果全部序列长度都为奇数,容易发现若先手取了其中一个序列的一个数,后手肯定再把这个序列的长度取回奇数。这是因为如果出现了长度为偶数的序列,那它肯定会成为先后手争夺的对象(双方都是成为先手比成为后手优)。所以全部序列的答案可以独立计算再加起来。
现在有一些序列长度为偶数,根据前面的讨论,它们会成为双方争夺的对象。取完偶数的序列后,就回到了上面的情况,并且先后手可能会交换顺序。设 \(x,y\) 为对于一个偶长序列,取头部和取尾部得到的剩下的序列的答案,设 \(mx = \max(x,y), mn = \min(x,y)\),发现肯定是按 \(mx - mn\) 从大到小先手交替地取。因为如果是 A 取了它,它会比 B 取它多了 \(mx - mn\) 的得分,反之如果 B 取了它,它会比 A 取它少 \(mx - mn\) 的得分。
这样最后的答案由两部分组成,一部分是奇长序列的答案,由于可以单独考虑,所以可以提前确定;另一部分是偶长序列的答案,需要先后手交替取完后转化为奇长序列再记入答案。
时间复杂度线性对数,瓶颈在于排序。
code
// Problem: F - Deque Game
// Contest: AtCoder - AtCoder Regular Contest 116
// URL: https://atcoder.jp/contests/arc116/tasks/arc116_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n;
vector<ll> vc[maxn];
inline bool cmp(pii a, pii b) {
return a.fst - a.scd > b.fst - b.scd;
}
inline ll calc(vector<ll> &a, int op) {
ll m = (ll)a.size();
if (!m) {
return 0;
} else if (m == 1) {
return a[0];
}
if (op) {
if (m & 1) {
return min(a[m / 2], max(a[m / 2 - 1], a[m / 2 + 1]));
} else {
return max(a[m / 2], a[m / 2 - 1]);
}
} else {
if (m & 1) {
return max(a[m / 2], min(a[m / 2 - 1], a[m / 2 + 1]));
} else {
return min(a[m / 2], a[m / 2 - 1]);
}
}
}
void solve() {
scanf("%lld", &n);
int c = 0;
for (int i = 1, k, x; i <= n; ++i) {
scanf("%d", &k);
while (k--) {
scanf("%d", &x);
vc[i].pb(x);
}
c += (vc[i].size() % 2 == 0);
}
vector<pii> S;
ll ans = 0;
if (c & 1) {
for (int i = 1; i <= n; ++i) {
if (vc[i].size() & 1) {
ans += calc(vc[i], 0);
continue;
}
auto a = vc[i], b = vc[i];
a.erase(a.begin());
b.pop_back();
ll x = calc(a, 0), y = calc(b, 0);
S.pb(max(x, y), min(x, y));
}
} else {
for (int i = 1; i <= n; ++i) {
if (vc[i].size() & 1) {
ans += calc(vc[i], 1);
continue;
}
auto a = vc[i], b = vc[i];
a.erase(a.begin());
b.pop_back();
ll x = calc(a, 1), y = calc(b, 1);
S.pb(max(x, y), min(x, y));
}
}
sort(S.begin(), S.end(), cmp);
for (int i = 0, o = 1; i < (int)S.size(); ++i, o ^= 1) {
ans += (o ? S[i].fst : S[i].scd);
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Deque Gameatcoder regular contest deque atcoder regular contest game atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder