AOJ 2142 : Bitwise Kingdom

問題リンク：Bitwise Kingdom | Aizu Online Judge

解法：
最初に求るビット列に何個１が含まれているのかを考える
Nビット中i個１を立てた時の組み合わせの数をどんどん足していき、和がM以上になった時点でループを打ち切る
(iは１の数で１から最大Nまで)

これで何個１を立てるかが分かったので、あとはそれをどこに配置するかを決める
ループで左から順に、その場所に０を置いたとするとその他の場所の１と０の組み合わせの数が求まるので
その数を加えたときに和がMを超えるか超えないかで０を置くか１を置くかを判断する

コード:

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1LL<<63)
#define MAX 70
#define deb(a) cout << #a << " " << a << endl

using namespace std;

typedef long long ll;

ll N,M;
ll C[MAX][MAX];

void makeC()
{
  C[0][0] = 1;
  rep(i,MAX-1)rep(j,i+1)
    {
      C[i+1][j] += C[i][j];
      if(j+1<MAX)C[i+1][j+1] += C[i][j];
    }
}

void compute()
{
  M--;
  if(M == 0)
    {
      cout << string(N,'0') << endl;
      return;
    }
  string ans = "";
  int NumberOfBits = 1;
  ll sum = 0;
  while(true)
    {
      sum += C[N][NumberOfBits]; 
      if(sum >= M)break;
      NumberOfBits++;
    }
  sum -= C[N][NumberOfBits];
  sum = M - sum;

  for(int i=N;i>=1;i--)
    {
      ll cost = sum - C[i-1][NumberOfBits];
      if(cost >  0)
	{
	  ans += "1";
	  sum -= C[i-1][NumberOfBits];
	  NumberOfBits--;
	}
      else ans += "0";
    }

  cout << ans << endl;
}

int main()
{
  makeC();

   while(cin >> N >> M,N|M)compute();

  return 0;
}