そしてそして方程式(SRM 542 div2 250pt)

二進数を使え！

　
photo by Christopher Chan

　今回は二進数を使います。

　TopCoder Statistics - Problem Statement

　ANDequationとは「かつ」「&」のことです。二進数で「1001&1110」なら「1000」となります。問題では、ベクトルに収納された整数を二進数に変換し、全ての要素を使い、「a&b&c…=n」となる形を探します。式のようになればnの数を返し、だめなら-1を返します。

　nは要素の中で最小の数になります。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;
 class ANDEquation{
    public:
     int restorY(vector <int> A){
         bitset<20> byAll;
         byAll.set();
         vector <int> ::iterator minA=min_element(A.begin(),A.end());
         int minP=distance(A.begin(),minA);
         long ba1=static_cast<long>(A[minP]);
         bitset<20> bymin(ba1);
         //cout <<byAll<<endl;
         for(int i=0;i<A.size();i++){
             if (i!=minP){
                 
                 bitset<20> by(A[i]);
           //      cout <<"by="<<A[i]<<endl<<by<<endl;
                 byAll=by&byAll;
          //       cout <<"byAll=" <<endl<<byAll<<endl;
             }
         }
         
         
       //  cout << "min="<<*minA<<endl;
        //cout <<minA<<endl;
        // cout <<bymin <<endl;
         
       //  if(bymin==byAll) {printf("ok\n");}else{printf("bad...\n");}
         return ((bymin==byAll)? *minA:-1);
         
        }
};

int main(){
    ANDEquation ob1;
    int a[]={2, 3, 7, 19};
    vector <int> b(a,a+4);
    ob1.restorY(b);
    return 0;
}

• • bitsetでlong型の整数を２進数に変換します。
  • min_elementを使い、vector内の最小の要素のイテレータを返します。
  • 最小の要素の添字を返すにはdistanceを使います。ベクトルの頭と最小の要素のイテレータの差を求めます。