Technocup 2019 - Elimination Round 1 E. Vasya and Good Sequences
解法
まず区間 を一つ固定して,この区間が条件を満たせるかの判定を考える.
ビットが立っている数が同じであれば作れる数字の集合は同じなため の値は本質ではなくビットが立っている数が大事. のビットが立っている数とする.
とできる方法があるかの判定は,
「色 のボールが 個あって違う色のボールをペアにできるとき,全てのボールがいずれかのペアに含まれるようなペアの作り方はあるか?」
という問題に帰着できる.この問題は が偶数 かつ であれば可能となる.
右端 に対してこの条件を満たす左端 が何個あるか?という問題を各 に対して解けばよい.
が偶数 となる左端 の個数は で合計が0/1となる区間 がそれぞれ何個あるかを管理しておくことで求められる.
を「満たさない」左端 は なことから に絞られ,全探索が可能である.
満たさない区間の長さが高々60なことに気づかなかった…
#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; vector<ll> a(n); REP(i, n) { ll t; cin >> t; a[i] = __builtin_popcountll(t); } ll ret = 0; vector<ll> parity(2); parity[a[0]%2]++; FOR(r, 1, n) { if(a[r]%2) swap(parity[0], parity[1]); // 条件を満たすlが何個あるか ll cnt = parity[0]; ll ma = a[r], sum = a[r]; for(ll l=r-1; l>=max(0LL,r-60); --l) { chmax(ma, a[l]); sum += a[l]; if(sum%2==0 && ma > sum/2) { cnt--; } } ret += cnt; parity[a[r]%2]++; } cout << ret << endl; return 0; }