SRM 590 Div1

Easy速く解かないとレートが維持できなくなってきた。

250 駒あそび？

RとLの駒を移動させて目的の形にできるか問題。

コード

#include <string>
#include <vector>
using namespace std;
class FoxAndChess{
public:
   string ableToMove(string begin, string target){
      if(solve(begin,target))
         return string("Possible");
      else
         return string("Impossible");
   }
   bool solve(string begin, string target){
      string str[2]={begin,target};
      vector<int> pos[2];
      vector<char> type[2];
      for(int j=0;j<2;j++)
      for(int i=0;i<str[j].size();i++){
         switch(str[j][i]){
         case 'R':
            type[j].push_back('R');
            pos[j].push_back(i);
            break;
         case 'L':
            type[j].push_back('L');
            pos[j].push_back(i);
            break;
         default:
            break;
         }
      }
      if(type[0]!=type[1])return false;
      for(int i=0;i<type[0].size();i++){
         if(type[0][i]=='R'){
            if(!(pos[0][i]<=pos[1][i]))return false;
         }
         else
            if(!(pos[0][i]>=pos[1][i]))return false;
      }
      return true;
   }
};
#include <iostream>
int main(){
   FoxAndChess f;
   cout<<f.ableToMove(string("R..."),string("..R."))<<endl;
   return 0;
}

500 XOR

XORで目的の数以下を作る方法は何通りあるか。

解法

与えられた数をnumber、目的の数をlimitとする。 ここで、numberの中からaとbをとってきてbの代わりにa+b(XOR)を入れても答えは変化しないという性質を使う。 numberを掃き出し法のように簡単にしていく。 以下の性質を持った状態に変形する。

• それぞれの要素の2進法での桁数が被らない。（その要素が0である場合を除く）
• ソート済み

次に以下のように元の問題をsum<=limitからsum=targetの小問題に分解する。

• numberをそのままでsum=limitとする。
• limitの1になっている桁を0に変え、その桁が一番下の桁になるように2の累乗で割る。さらに同じだけnumberを割る。そして、sum=limitとする。

それぞれの小問題はnumberを大きい方から貪欲的にとっていけばよい。

コード

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
int bit(long long value,long long n){
   return (value>>n)&1;
}
//for test
void print(vector<long long> n){
   for(int i=0;i<n.size();i++){
      for(int j=3;j>=0;j--)
         cout<<bit(n[i],j);
      cout<<" ";
   }
   cout<<endl;
}
class XorCards{
public:
   long long count(vector<long long>& number,long long target,int star){
      long long ans=1;
      for(int i=0;i<number.size();i++){
         long long upper=number[i]>>star;
         if(upper==0){ans*=2;continue;}
         if((target^upper)<target)target^=upper;
      }
      if(target==0)
         return ans;
      else
         return 0;
   }
   long long numberOfWays(vector<long long> number, long long limit){
      for(int i=63;i>=0;i--){ 
         sort(number.begin(),number.end());
         for(int j=0;j<number.size();j++){
            if(bit(number[j],i)==1){
               for(int k=j+1;k<number.size();k++)
                  if(bit(number[k],i)==1)
                     number[k]=number[k]^number[j];
               break;
            }
         }
      }
      sort(number.begin(),number.end(),greater<long long>());
      long long ans=0;
      ans+=count(number,limit,0);
      for(int i=0;i<64;i++){
         if(bit(limit,i)==1)
            ans+=count(number,(limit>>i)^1,i);
      }
      return ans;
   }
};
int main(){
   XorCards x;
   long long vv[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
   vector<long long> v(sizeof(vv)/sizeof(vv[0]));
   for(int i=0;i<v.size();i++)
      v[i]=vv[i];
   long long l=1000000000000000;
   cout<<x.numberOfWays(v,l);
   return 0;
}