AOJ2142 Bitwise Kingdom

問題リンク Bitwise Kingdom

• 概要

[0, 2^N)の整数を表すN文字のビット文字列の中でM番目に小さいものを求めよ。
ただし、文字列の比較順序は次の順序で行われる
1. 文字列中に含まれる1の数が多い方が大きい
2. 1の数が同じならば辞書式で大きい方が大きい
1 <= N <= 60
1 <= M <= 2^M

• 解法

与えられたNとMを使えば、M番目の文字列に含まれる1の個数Cが分かります。すると、C個の1を含む、長さNのビット文字列の中でM'番目に小さいものを求めるという問題に変わります。
この文字列を再帰を使って求めます。
再帰には、「L番目〜R番目の文字列を作ることができる」という範囲を引数に持たせておきます。
使っていない1の個数がcで、k番目のインデックスの文字を決める場合を考えます。
まず、[L,R]の中にM'が無ければ作ることができません。刈ります。
次に、k番目の文字を0としてみます。このとき、作ることができる文字列の範囲は上限が狭まります。k番目を1とした場合に作ることができる文字列の種類はn-k-1Ccであり、この数だけ上限が狭まることになります。つまり、[L,R]だった作成可能範囲が[L, L+(n-k-1Cc)-1]になります。
k番目を1としてみます。今度は、下限が狭まります。k番目を0としたときに作ることができる文字列の種類はn-k-1Ccであり、この数だけ下限が狭まります。[L,R]だった範囲が[L+(n-k-1Cc), R]になります。

• ソース

import java.util.Scanner;

//Bitwise Kingdom
public class AOJ2142 {

	int n;
	long M;
	char[] r;
	long[][] comb;

	boolean dfs(int k, long L, long R, int c){
		if(!(L<=M&&M<=R))return false;
		if(k==n){
			return c==0;
		}
		if(n-k-1>=c){
			r[k] = '0';
			if(dfs(k+1, L, L+comb[n-k-1][c]-1, c))return true;
		}
		if(c==0)return false;
		r[k] = '1';
		long up = 0;
		if(n-k-1>=c)up += comb[n-k-1][c];
		return dfs(k+1, L+up, R, c-1);
	}

	long[][] comb(int N){
		long[][] r = new long[N+1][N+1];
		r[0][0]=1;
		for(int i=1;i<=N;i++){
			r[i][0]=r[i][i]=1;
			for(int j=1;j<i;j++){
				r[i][j] = r[i-1][j-1]+r[i-1][j];
			}
		}
		return r;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		comb = comb(60);
		for(;;){
			n = sc.nextInt(); M = sc.nextLong();
			if((n|M)==0)break;
			long s = 0;
			int c = 0;
			for(;c<=n;c++){
				s += comb[n][c];
				if(M<=s)break;
			}
			s -= comb[n][c];
			M -= s;
			r = new char[n];
			dfs(0, 1, comb[n][c], c);
			System.out.println(new String(r));
		}
	}

	public static void main(String[] args) {
		new AOJ2142().run();
	}
}