AGC015D A or...or B Problem(900)

atcoder.jp

問題

整数が与えられます。以上以下の整数から個以上選んで、それらのbitwise orを取ってできる整数としてありうるものが何通りあるかを求めてください。

制約

• 

考察

の場合は通りなので、の場合を考えます。

が上位桁まで一致していたとします。以上以下の数の上位桁はこれと等しいので、bitwise orを取った結果の上位桁も必ずこれに一致します。よって上位桁は無かったことにしても問題ありません。

上位桁を除くと、より、の最上位のビットは、の最上位のビットはです。

以上以下の整数を最上位のビットがのグループと、のグループに分けてみます。(1)最上位のビットがのグループから選ぶ場合、(2)最上位のビットがのグループから選ぶ場合、(3)両方から選ぶ場合、の3通りの場合を考えます。

最上位のビットがで、それ以外のビットがの数をとすることにします。

(1)最上位のビットがのグループから選ぶ場合
bitwise orを取ることによって数が小さくなることはないので、最小値はです。また最上位のビットを立てることはできないので、最大値はです。この間に含まれる数は全て作ることができます(その数自身を選べばよいです)。

(2)最上位のビットがのグループから選ぶ場合
最小値はです。すべての数を選んだときに最大になって、これはの上から番目の立っているビット以下を立てた整数です。これをとします。以上以下の整数は全て作ることができます。なぜなら、との間に、最上位のビットと、(の番目に立っているビット以下の)あるビットのみが立っているような整数が存在するからです。とこれらの整数を組み合わせることによって、以上以下の全ての整数を作ることができます。

(3)両方から選ぶ場合
まず最小値について考えます。bitwise orを取ることによって数が小さくなることはないので、各グループから一つずつ選ぶ場合を考えれば良いです。最上位のビットがのグループから選ぶべき整数はです。もう一方のグループから選ぶ数との両方で立っているビットは存在しないので、これらのbitwise orは単純に和になります。よって最小値はだと分かります。また最大値はすべてのビットが立っている数で、これはです。この間の整数は全て作ることができます(とを選ぶ、とを選ぶ、、とを選ぶというようにすればよいです)。

以上より、作れる整数の区間は(1)、(2)、(3)の3つであることが分かりました。あとはこれらの区間の和集合を求めれば良いです。(2)と(3)は交差するときがあるので、場合分けをするか、重複を引く必要があります。

#include<bits/stdc++.h>
using namespace std;
 
using lint=long long;
 
lint get(lint l,lint r){ return r-l+1; }
 
int main()
{
   lint A,B; cin>>A>>B;
   if(A==B){ cout<<1<<endl; return 0; }
 
   const int LOG=60;
   lint X=0,Y=0;
   for(int i=LOG-1;i>=0;i--){
      if((A>>i&1)==(B>>i&1)){
         if(A>>i&1){
            A-=1LL<<i;
            B-=1LL<<i;
         }
      }else{
         X=Y=1LL<<i;
         bool flag=false;
         for(int j=i-1;j>=0;j--){
            if(B>>j&1) flag=true;
            if(flag) Y|=1LL<<j;
         }
         break;
      }
   }
   lint ans=get(A,X-1);
   if(Y<X+A) ans+=get(X,Y)+get(X+A,2*X-1);
   else ans+=get(X,2*X-1);
   cout<<ans<<endl;
   return 0;
}

まとめ

• bitwise orを取って小さくなることはない()
• 数え上げで、答えが区間になる

感想

バチャ中に見たときは何をすればいいのか全然分かりませんでした。答えが区間になることが予想できたら、最小値と最大値は何か、その間の数を全部作れるという考察方法を学びました。「最上位のビットで二つのグループに分ける」という考えがどこから出てきたのかがよく分かりませんでしたが、(公式解説にあるように)bitwise orを取った結果が以上になると分かったときに、「どこまでなら作れるか」ということを考えたら思いつけるのかなと思いました。