SRM699 Div1 Easy OthersXor - ちゃっくのメモ帳

問題

要はN個の数字があり入力x[i]にはi番目の数字以外の数字のxorを取ったものが入っている。
入力xを満たすようなN個の数字の組み合わせのうち合計が最小となるようなものを見つけその最小値を求める(ただしそのようなN個の数字がなければ-1を返す)

解説

神ペーパーさんに教えて貰った。
各bitを個別に考えることができる(xorをとってるので繰り上がり、繰り下がりが発生することはない).
そして、数列の要素のうちiビット目が1のものがいくつあるかをそれぞれのbitについて確かめればいい。

それぞれのbitについて1がk個でxの条件を成立できるかを確かめ、成立できるkのうち最小のものを求めればよく、k個で可能かどうかは
kが奇数かつ x[i]%2=1 なら　i番目の数字の見ているビットは0(自分以外が奇数個)
kが偶数かつ x[i]%2=1 なら i番目の数字の見ているビットは1(自分以外は偶数個)
(あとkが偶数/奇数で x[i]%2==0のときも考える)
としていって確かめればよい

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

const int BITS = 30;

class OthersXor{
    public:
        long long minSum(vector<int> x){
            int N = x.size();
            ll sum=0;
            vector<vector<int>> ans(N,vector<int>(30,-1));
            vector<int> cnt(BITS);

            rep(i,BITS){
                // see i-bit
                bool f=false;
                for(int num=0;num<=N;num++){
                    // num個にできる?
                    int ones = 0;
                    int undefine = 0;
                    for(int j=0;j<N;j++){
                        if(x[j]==-1){
                            undefine++;
                            continue;
                        }
                        // x[j]をみる
                        int b = (x[j]>>i) & 1;
                        if(num%2==1 and b==0){
                            ones++;
                        }else if(num%2==0 and b==1){
                            ones++;
                        }
                    }
                    if(ones > num) continue;
                    if(undefine < num-ones) continue;
                    for(int j=0;j<N;j++){
                        if(x[j]==-1) ones++;
                        if(ones == num) break;
                    }
                    f=true;
                    cnt[i] = num;
                    break;
                }
                if(!f) return -1;
            }

            for(int i=0;i<BITS;i++){
                ll t = 1 << i;
                sum += t * cnt[i];
            }
            return sum;
        }
};

感想

はじめてのDiv1だったから1問くらい解きたかった....

1問くらい解けないと緑に戻ってしまうだろうし怖い...