考虑若 \(n\) 是奇数怎么做。枚举 Alice 第一次选的数 \(a_i\),然后考虑把剩下的数两两结成一个匹配,若 Bob 选了其中一个,Alice 就选另一个。容易发现排序后奇数位和它右边的偶数位匹配最优。那么设奇数位的和为 \(A\),偶数位的和为 \(B\),此时 Alice 获胜当且仅当 \(L \le A + a_i \land B + a_i \le R\)。
若 \(n\) 是偶数,仍然考虑沿用上面的做法,把数结成匹配做。仍然枚举 Alice 第一次选的数,和这个数匹配的数,那么剩下的数仍然奇数位匹配右边偶数位最优。若 Bob 选了这个数匹配的数,Alice 可以新开一个匹配,否则 Alice 选 Bob 选的数匹配的数即可。
需要枚举 Alice 第一次选的数和这个数匹配的数,复杂度 \(O(n^2)\)。
code
// Problem: D - Subset Sum Game
// Contest: AtCoder - AtCoder Grand Contest 056
// URL: https://atcoder.jp/contests/agc056/tasks/agc056_d
// 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 mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5050;
ll n, L, R, a[maxn], b[maxn];
void solve() {
scanf("%lld%lld%lld", &n, &L, &R);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
int m = 0;
for (int j = 1; j <= n; ++j) {
if (i != j) {
b[++m] = a[j];
}
}
ll s1 = a[i], s2 = a[i], t1 = 0, t2 = 0;
for (int j = 1; j <= m; ++j) {
((j & 1) ? t1 : t2) += b[j];
}
for (int j = 1; j <= m; ++j) {
((j & 1) ? t1 : t2) -= b[j];
if (L <= s1 + t2 && s2 + t1 <= R) {
puts("Alice");
return;
}
((j & 1) ? s1 : s2) += b[j];
}
}
puts("Bob");
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Contest Subset Grand Gameatcoder contest subset grand authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 001 atcoder contest grand 022 atcoder contest grand 039 avoidance atcoder contest grand histogram atcoder contest grand atcoder contest grand 019