AtCoder AGC #015 : D - A or...or B Problem

いつもの桁DPと思い込み過ぎた。
http://agc015.contest.atcoder.jp/tasks/agc015_d

問題

閉区間[A,B]の範囲の整数を1つ以上選択し、それらのbitwise-orを取ることで得られる値は何通りか。

解法

f(A,B) := 閉区間[A,B]の範囲の整数を1つ以上選択し、それらのbitwise-orを取ることで得られる値
とする。

Bの最上位ビットをxとする。
Aもxの桁を持つ場合、どれを選んでもxのビットは立つのでf(A,B) = f(A^x,B^x)となり、探索する値を小さくすることができる。

以下そうでない場合を考える。
まず、複数の値のbitwise-orを取ると、最低でもそれらの最大値以上となることを前提とする。

• orを取る際xのビットを取らないようにする場合
  • [A,x-1]の範囲のbitwise-orで得られる値なので、上記前提より[A,x-1]の(x-A)通り。
• orを取る際xのビットを取るようにする場合
  • [x,B]の範囲の数値のみ使う場合を考える。xの次に立っているビット、すなわち(B-x)のMSBをyとすると、[x,x+2*y-1]の範囲の値がとれる。
  • [A,x-1]と[x,B]両方の範囲の値を取る場合、[x+A,2*x-1]の範囲の値がとれる。
  • 上記2つの範囲は重複することもあるので注意。

ll hoge(ll L,ll R) {
	if(L==R) return 1;
	
	ll r=1;
	while(r*2<=R) r*=2;
	
	if(L&r) return hoge(L^r,R^r);
	
	ll k=1;
	while(k<=(R^r)) k*=2;
	
	//only a
	ll ret=r-L;
	
	// only B
	ll x=r,y=r+k-1;
	// A+B
	ll a=r+L,b=2*r-1;
	
	if(y<a) return ret+y-x+1+b-a+1;
	else return ret+b-x+1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	ll A,B;
	
	cin>>A>>B;
	cout<<hoge(A,B)<<endl;
}

まとめ

うーん、頭が固かった。