Codeforces Round #557 (Div. 2) [based on Forethought Future Cup - Final Round] C. Thanos Nim
解法
どのような状態が勝ち/負けなのか考える。n=6で試してみる。0が4個以上の場合操作できないのでその時点で負けである。0が3個以下の場合、0が4個以上になるように操作して相手に渡せばよいので勝ちになる。1が4個以上の場合、どう操作しても0が3個以下の状態にしか移動できないので負けになる。1が3個以下の場合、1が4個以上になるように操作して渡せば良いので勝ちである。
0 0 0 0 0 0 → 負け
0 0 0 0 0 ? → 負け
0 0 0 0 ? ? → 負け
0 0 0 ? ? ? → 勝ち
0 0 ? ? ? ? → 勝ち
0 ? ? ? ? ? → 勝ち
1 1 1 1 1 1 → 負け
1 1 1 1 1 ? → 負け
1 1 1 1 ? ? → 負け
1 1 1 ? ? ? → 勝ち
1 1 ? ? ? ? → 勝ち
1 ? ? ? ? ? → 勝ち
以上のように実験より最小の要素がn/2個以下であれば勝ち、n/2個より多ければ負けなことがわかる。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a) { out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(const T &i: a) out<<i<<','; out<<']'; return out; } template<class T> ostream &operator <<(ostream& out, const set<T>& a) { out<<'{'; for(const T &i: a) out<<i<<','; out<<'}'; return out; } template<class T, class S> ostream &operator <<(ostream& out, const map<T,S>& a) { out<<'{'; for(auto &i: a) out<<i<<','; out<<'}'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; ll mi = LLINF, cnt = 0; REP(i, n) { ll a; cin >> a; if(mi > a) mi = a, cnt = 1; else if(mi == a) cnt++; } if(cnt <= n/2) cout << "Alice" << endl; else cout << "Bob" << endl; return 0; }