TopCoder SRM600 Div1Easy ORSolitaire [1人競技プログラミング Advent Calendar 2016 1日目]

この記事は1人競技プログラミング Advent Calendar 2016 1日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement

X=0から始まり、numbers配列から任意の1つの数字を選び、Xと選んだ数字のorでXを上書きしていく。 Xとgoalの値が一致したらゲームクリアとなる。

numbersから数値をいくつか取り除き、ゲームをクリア出来ないようにしたい。 numbersから最小何個の数値を取り除けばゲームクリア出来なくなるかを答えよ。

解いた方法：
orでXを上書きするということは、Xからgoalまでに使用出来る数は必ずgoalのbitと同じbitが立っている必要がある。 使用する数の方でbitが不足しているのは問題ないが、goalに立っていないbitが立っている数は使用できない。

例えば2番目のサンプルの numbers = [1,2,4,8] goal = 7 の場合において8をbitにすると1000になり、7をbitにすると0111となる。 この場合、8(1000)を使用するとor演算ではbitを消すことが出来ない為、7(0100)にすることが出来なくなる。

また、何処かのbitが1か所でも立たなくなればgoalの数を作ることが出来ない。 その為、上記で使用できる数を列挙し、goalで使用する各bitの位置において使用している数を求めて一番少ない数が答えとなる。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

VI to_bit_vector(int num){
    VI res;
    while(res.size() != 32){
        res.PB( num % 2 == 0 ? 0 : 1);
        num /= 2;
    }
    return res;
}

class ORSolitaire {
    public:
    vector<int> numbers;
    int goal;
    int getMinimum(vector<int> _numbers, int _goal) {
        numbers = _numbers, goal = _goal;
        VI goal_bit = to_bit_vector(goal);


        int ans = INF;
        REP(i, 32){
            if(goal_bit[i] == 0) continue;

            int bit_count = 0;
            REP(j, numbers.size()){
                VI check_bit_number = to_bit_vector(numbers[j]);
                if(check_bit_number[i] == 0) continue;

                bool flag = true;
                REP(k, 32){
                    if(goal_bit[k] == 0 && check_bit_number[k] == 1){
                        flag = false;
                        break;
                    }
                }

                if(!flag) continue;
                bit_count++;
            }

            ans = min(ans, bit_count);
        }

        return ans;
    }
};