Google Code Jam 2014 Round 1B : B. New Lottery Game

なんかCodeforcesに出そうな問題。
https://code.google.com/codejam/contest/2994486/dashboard#s=p1

問題

自然数A,B,Kが与えられる。
0 ≤ x < A、0 ≤ y < Bとなる(x,y)のペアのうち、x and y < Kとなるものの組み合わせ数を答えよ。

解法

上の桁から桁DPしていけばよい。
どこかの桁でKが1の時、x and yの桁が0になるものを列挙すればよい。
よってKのn桁目が：

• 1の時：
  • xもyも2^n以上の場合、x and yのn桁目は1になるので、まだK未満になるか確定しない。(A-2^n),(B-2^n),(K-2^n)に対して再帰的に処理していく。
  • それ以外は常にK未満になるので答えにカウントする。
• 0の時
  • xもyも2^n以上の場合、x and yのn桁目は1になるので、絶対にK未満にならない。
  • それ以外の場合、以下の結果を加算すればよい。
    • xが2^n以上でyが2^n未満 ： A=A-(2^n)として(n-1)桁目を再帰的に処理
    • xが2^n未満でyが2^n以上 ： B=B-(2^n)として(n-1)桁目を再帰的に処理
    • xが2^n未満でyも2^n未満 ： (n-1)桁目を再帰的に処理

ll A,B,K;

ll dodo(ll A,ll B,int dig) {
	ll D=1LL<<dig;
	if(dig==-1) return 1;
	ll ret=0;
	if(K&D) {
		if(A>=D && B>=D) ret=dodo(A-D,B-D,dig-1);
		if(A>=D) ret+=(A-D+1)*(min(B,D-1)+1);
		if(B>=D) ret+=(B-D+1)*(min(A,D-1)+1);
		ret+=(min(A,D-1)+1)*(min(B,D-1)+1);
	}
	else {
		if(A>=D) ret+=dodo(A-D,min(B,D-1),dig-1);
		if(B>=D) ret+=dodo(min(A,D-1),B-D,dig-1);
		ret+=dodo(min(A,D-1),min(B,D-1),dig-1);
	}
	return ret;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>A>>B>>K;
	A--,B--,K--;
	
	_P("Case #%d: %lld\n",_loop,dodo(A,B,29));
}

まとめ

andやxorの問題が出たら即桁DP、というのはCodeforcesで良く出るね。