SRM699 div1 easy OthersXor

考えたこと

• 桁別に独立に見てよさそう
• (0, 0, 0, 1, 1, 1) みたいなのについて考えてみる
• 0の個数が奇数なら0のところを1に、1のところを0にすれば条件を満たしそう
• 逆にこれ以外の構成ある？
• 0のところに0が当てはまっているものと1が当てはまっているものがあるとまず不可能
• 上の例で (0, 1, ?, ?, ?, ?) みたいな構成をつくりたいとすると?の部分で1の個数の偶奇について矛盾
• ということは各bitごとに0と1と-1の個数を数えて場合分けするとよさそう
• 0の個数が奇数ならその分を答えに足す、偶数なら-1みたいなのを書く
• sampleで落ちる
• 0の個数が偶数でも-1が存在すればそこを1にすれば構成できそう
• まだsampleで落ちる
• 1の個数が奇数のときも1に1、0に0みたいな当てはめ方をすれば構成できそう
• sampleが通る
• 投げると通る

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#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()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

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); }

class OthersXor {
   public:
   long long minSum(vector <int> x)
  {
    int n = x.size();
    ll ret = 0;
    REP(bit, 30) {
      ll one = 0, zero = 0, both = 0;
      REP(i, n) {
        if(x[i] == -1) both++;
        else if(x[i]>>bit&1) one++;
        else zero++;
      }
      if(one==0) continue;
      ll plus = LLINF;
      if(zero%2) chmin(plus, zero*(1LL<<bit));
      if(zero%2==0 && both) chmin(plus, (zero+1)*(1LL<<bit));
      if(one%2==0) chmin(plus, one*(1LL<<bit));
      if(one%2 && both) chmin(plus, (one+1)*(1LL<<bit));
      if(plus==LLINF) return -1;
      ret += plus;
    }
    return ret;
  }
};