Codeforces #247 Div2 D. Random Task

この問題は２位に5分近く差をつけてFirst Answerを取れたのでよかった。
http://codeforces.com/contest/431/problem/D

問題

ある数nに対し、(n+1),(n+2),...,2*nの数列を考える。
これらの各数列の各要素の２進数表記を考えたとき、ビットがK個立つ数がM個となるようなnを答えよ。

解法

数X以下でK個ビットが立つ数値の数をS(X,K)と表すなら、この問題はS(2*n,K)-S(n,K)==MとなるNを求めればよい。

まず、nに対しS(2*n,K)-S(n,K)は単調増加であることを示す。
nに対し(n+1)～2nの数列が定義され、(n+1)に対しては(n+2)～(2(n+1))の数列が定義される。
ここで、(n+1)と2(n+1)は倍半分の関係にあるので、２進数表記でビットが立つ数は等しい。
よって、後者は2n+1の分だけあるビット数の立つ数が１個増える。

nに対しビットがK個立つ数が単調増加なので、後はnを二分探索して条件を満たすものを見つければよい。
S(x,K)は以下のように求められる。
xを２進数表記したとき、MSB以下の桁をyyyyyと表現し、全体で1yyyyyyと表現できたとする。
yyyyyyの桁数をDと置く。

• 1000000未満の数、すなわち0～(2^D-1)の間は、ビットがK個立つ数が条件を満たすので、その数は
• 1000000～1yyyyyyyにおいては、先頭桁のビットが1個立っているので残りの桁が(K-1)個ビットが立つよう、S(yyyyyy,K-1)を再帰的に計算すればよい。

ll M,K;

ll comb(int P_,int Q_) {
	static const int N_=65;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

ll calc(ll val,int D) {
	int d=0;
	
	if(D==0) return val==0;
	if(val==0) return 0;
	
	while((1LL<<(d+1))<=val) d++;
	return comb(d,D)+calc(val-(1LL<<d),D-1);
}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>M>>K;
	ll L=0,R=1000000000LL*1000000000LL;
	
	while(L<R) {
		ll mi=(L+R)/2;
		ll res=calc(mi*2,K)-calc(mi,K);
		if(res==M) {
			cout << mi << endl;
			return;
		}
		else if(res<M) L=mi+1;
		else if(res>M) R=mi;
	}
}

まとめ

これはすんなり解けてよかったね。