GCJ 2016 Round 1C B. Slides!

2016/05/08 (Sun) GCJ 構築 グラフ

問題

問題文

頂点数 $B$ の有向グラフで頂点 $0$ から頂点 $B-1$ までの道の数が $M$ 個であるものを構築してください．

方針

有向閉路ができると無限に道が増えるので DAG にならないといけない． まず，$B$ 個の頂点でできる道の個数の最大値は $2^{B-2}$ 個になる． そのようなグラフは， $E = \{ (u,v) | u < v \}$ のように構成できる． $M$ の立っているビットを見て，$0$ から他の頂点への辺のつなぎ方を調整することで， $2^{B-2}$ 以下の任意の数が構築できる．

実装

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

vvi solve(int B, ll M) {
    vvi mat(B, vi(B));
    for (int i = 0; i < B; ++i) {
        for (int j = i + 1; j < B; ++j) {
            mat[i][j] = 1;
        }
    }
    if (1LL << (B - 2) < M) return {};
    if (1LL << (B - 2) == M) {
        mat[0][B - 1] = 1;
        --M;
    } else {
        mat[0][B - 1] = 0;
    }
    for(int i = B - 2; i >= 1; --i){
        if (~M & 1) mat[0][i] = 0;
        M /= 2;
    }
    return mat;
}

int main(){
    int T;
    cin >> T;
    rep(it, T) {
        ll B, M;
        cin >> B >> M;
        cout << "Case #" << it + 1 << ':';
        auto ans = solve(B, M);
        cout << ' ' << (ans.size() ? "POSSIBLE" : "IMPOSSIBLE") << endl;
        if (ans.size()) {
            for (int i = 0; i < B; ++i) {
                for (int j = 0; j < B; ++j) {
                    cout << ans[i][j];
                }
                cout << endl;
            }
        }
    }
}