TopCoder SRM 595 Div2 Hard LittleElephantAndXor - kmjp's blog

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 595 Div2 Hard LittleElephantAndXor

SRM

なんかCodeforcesで似た問題やったことある。
http://community.topcoder.com/stat?c=problem_statement&pm=12623

問題

３つの非負整数A,B,Cが与えられる。0<=X<=Aかつ0<=Y<=Bとなる整数(X,Y)の組のうち、 X xor Y <= Cとなるものを答えよ。

解法

xorで処理する問題はbit単位でループ回すのが定番だよね。
ということで、A,B,Cについて上の桁から順次処理をしていく。

(i+1)桁までの処理が終わり、A,B,Cは(i+1)桁より上のビットが立ってないとする。
簡単にするために、A>Bという過程を置く。
A,B,Cのi桁目の値をAi,Bi,Ciと置き、A,B,Cのi桁目を消した状態で以下の場合分けをする。

  • Ci==1の時
    • この時、X^Yのi桁目を0にすれば、確実にX^Y
    • Ai==Bi==1の時：
      • XiとYiを両方0にすると、(i-1)桁目以下は何を選んでもX^Y
      • XiとYiを両方1にした場合、(i-1)桁目以下は(0～A)、(0～B)の何を選んでも良いので、(A+1)*(B*1)通り
      • Xiが0、Yiが1にする場合、Yの(i-1)桁目以下は(0～B)しか選べないが、Xは(0～(1<<(i-1))-1)のどれでも選べる。よって、各YについてXを(0～(1<<(i-1))-1)通りすべて選ぶと、C以下になるのは(C+1)通りになる。よって掛け合わせて(B+1)(C+1)個選べる。
      • Xiが1、Yiが0にする場合上記の逆で(A+1)(C+1)個選べる。
      • 以上の４つの値を足したらそれで終了、ループから抜ける。
    • Ai==1、Bi==0の時：
      • XiとYiに両方0を選ぶ場合、Xの(i-1)桁目以下は任意に選べるので(B+1)(1<<(i-1))通り。
      • Xiが1、Yiに0を選ぶ場合、まだXi^Yi==Ciなので小さくできるかわからない。よってループを継続する。
    • Ai==0、Bi==0の時：
      • XとYに何を選んでもi桁目は0なので、(A+1)(B+1)通り。
  • Ci==0の時
    • この時、X^Yのi桁目を0にしてもまだX^YCなので不可。
    • Ai==Bi==1の時：
      • XiとYiを両方0にすると、XとYの(i-1)桁目以下は任意に選べるので、Xを(1<<(i-1))通り全て選んだ時、YはX^Y<=Cとなるものが(C+1)通り選べる。よって(1<<(i-1))(C+1)通り。
      • XiとYiを両方1にした場合、Xi^Yi==0なのでループを継続
    • Ai==1、Bi==0の時：
      • Yの(i-1)桁目以下は(0～B)しか選べないが、Xは(0～(1<<(i-1))-1)のどれでも選べる。よって、X^Y<=Cとなるのは(B+1)(C+1)個選べる。
    • Ai==0、Bi==0の時：
      • Xi^Yi==Ci二しかならないので、次のループに行く。
  • 最終的にループを途中で抜けないとA==B==C==0になるので、最後に場合の数に1を加算。

上記場合分けをコードに起こすと下記のようになる。

class LittleElephantAndXor {
	public:
	long long getNumber(int A, int B, int C) {
		ll ret=0;
		int la,lb,lc,i;
		
		for(i=29;i>=0;i--) {
			if(A<B) swap(A,B);
			la=A&(1<<i),lb=B&(1<<i),lc=C&(1<<i);
			A-=la; B-=lb; C-=lc;
			
			if(lc) {
				if(lb) {
					ret += (1LL<<(2*i)); // la==0 && lb==0
					ret += (B+1)*(ll)(C+1); // la==0 && lb==1 
					ret += (A+1)*(ll)(C+1); // la==1 && lb==0 
					ret += (A+1)*(ll)(B+1); // la==1 && lb==1 
					return ret;
				}
				else if(la) {
					ret += (1LL<<i)*(ll)(B+1); // la==0 && lb==0
					// la==1 && lb==0
				}
				else {
					ret += (A+1)*(ll)(B+1); // la==0 && lb==0
					return ret;
				}
			}
			else {
				if(lb) {
					ret += (1LL<<i)*(C+1); //la==0 && lb==0
					//la==1 && lb==1
				}
				else if(la) {
					ret += (B+1)*(ll)(C+1); //la==0 && lb==0
					return ret;
				}
			}
		}
		return ret + 1;
	}
};

まとめ

場合分けが結構面倒。