GCJ 2016 Round 1C B: Slides!

問題

Dashboard - Round 1C 2016 - Google Code Jam

解法

閉路があると無限ループしてしまうので、求めるグラフはDAGである。よってビル番号の小さい方から大きい方へ移動することにする。

1〜N-1とBのN個の頂点で可能な辺を全て張ってDAGを作ると、1からBへの行き方は通りになる。ここにさらに頂点Nを追加する事を考える。Nから移動できる頂点はBのみなので、辺N->Bを張る。

• 1->Nを張ると、1->N->Bの1通りが増える。
• 2->Nを張ると、1->2->N->Bの1通りが増える。
• 3->Nを張ると、1->...->3->N->Bの2通りが増える。
• 4->Nを張ると、1->...->4->N->Bの4通りが増える。
• ...

この要領で、求めるべきM通りのうちはN個の頂点の部分グラフによって構成し、残ったパターンは頂点Nへの辺の張り方を選んで調節すれば良い。

コード

#include <bits/stdc++.h>
using namespace std;

int64_t fast_pow(int64_t x, int64_t e) {
  int64_t ret = 1;
  int64_t cur = x;
  while (e) {
    if (e & 1) ret *= cur;
    cur *= cur;
    e >>= 1;
  }
  return ret;
}

int64_t dp_check(const vector<vector<bool>> &ans) {
  int N = ans.size();
  vector<int64_t> dp(N, 0);
  dp[0] = 1;

  for (int i = 1; i < N; ++i) {
    for (int j = 0; j < i; ++j) {
      if (ans[j][i]) dp[i] += dp[j];
    }
  }
  return dp[N - 1];
}

vector<vector<bool>> solve(int B, int64_t M) {
  int64_t checkM = M;
  if (fast_pow(2, B - 2) < M) return vector<vector<bool>>();
  vector<vector<bool>> ans(B, vector<bool>(B, false));

  int init = 0;
  while (fast_pow(2, init + 1) <= M) init++;
  for (int i = 0; i <= init; ++i) {
    ans[i][B - 1] = true;
    for (int j = i + 1; j <= init; ++j) {
      ans[i][j] = true;
    }
  }
  M -= fast_pow(2, init);

  int add = init + 1;
  for (int i = init; i > 0; --i) {
    if (M >= fast_pow(2, i - 1)) {
      ans[i][add] = true;
      ans[add][B - 1] = true;
      M -= fast_pow(2, i - 1);
    }
  }
  if (M == 1) ans[0][add] = true;

  if (checkM != dp_check(ans)) {
    cerr << B << " " << checkM << endl;
    for (int i = 0; i < ans.size(); ++i) {
      for (int j = 0; j < ans[i].size(); ++j) {
        if (ans[i][j])
          cerr << 1;
        else
          cerr << 0;
      }
      cerr << endl;
    }
  }
  return ans;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int T;
  cin >> T;
  for (int testcase = 1; testcase <= T; ++testcase) {
    int B;
    int64_t M;
    cin >> B >> M;

    cout << "Case #" << testcase << ": ";
    vector<vector<bool>> ans = solve(B, M);
    if (ans.size() == 0) {
      cout << "IMPOSSIBLE" << endl;
    } else {
      cout << "POSSIBLE" << endl;
      for (int i = 0; i < ans.size(); ++i) {
        for (int j = 0; j < ans[i].size(); ++j) {
          if (ans[i][j])
            cout << 1;
          else
            cout << 0;
        }
        cout << endl;
      }
    }
  }
}