Google Code Jam Round 1C B:Slides!

問題

https://code.google.com/codejam/contest/4314486/dashboard#s=p1
B個の建物があって、それぞれの建物の間に一方通行の動く歩道を作ることを考えている。
建物1から建物Bまでの経路数がちょうどMになるような歩道の引き方を一つ出力せよ。

考えたこと

1からBまでの経路上にループとなる部分が1つでもあると解は無限になるため、基本はループは考えないで良い。
この場合の最大ケースとして、
iがjより小さい任意のi,jについてiからjへの経路を構築した場合を考えると、1からBまでの経路数はであるとわかる。
なので、まずはMがこれより大きい場合についてはIMPOSSIBLEを返して良い。
次に、の内訳を調べてみると、以下の総和として分解できる。
1->Bの枝を引いた場合：1通り
2->Bの枝を引いた場合：1通り
3->Bの枝を引いた場合：2通り
以下同様に、
n->Bの枝を引いた場合：通り

よって、Mの2進数表記を舐めながら対応する部分の枝を張って上げれば良い。

コード

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   long long B,M;
   cin >> B >> M;
   if( M > (1LL<<(B-2)) ){
      cout << "Case #" << loop+1 << ": " <<"IMPOSSIBLE"<< endl;
      continue;
   }
   cout << "Case #" << loop+1 << ": " <<"POSSIBLE"<< endl;
   for( int i = 0 ; i < B-1; i++ ){
      for( int j = 0 ; j < B-1; j++ ){
         if( i<j ) cout <<"1";
         else cout <<"0";
      }
      if( i==0 && M==(1LL<<(B-2)) ){
         cout <<"1";
         M--;
      }
      else if( i>0 && (M&(1LL<<(i-1)))){
         cout <<"1";
      }
      else{
         cout <<"0";
      }
      cout <<endl;
   }
   for( int i = 0 ; i < B; i++ ){
      cout <<"0";
   }
   cout << endl;
  }
  return 0;
}