Google Code Jam 2016 Round1C B Slides!

https://code.google.com/codejam/contest/4314486/dashboard#s=p1
　全く分かりませんでした。というか、人間が解ける問題に見えませんでした。
1からBまでM通りの行き方があるグラフの隣接行列をつくれ、という問題。

　こんな感じで、あるノードを付け足すごとに、すでにあったノードに全部に辺を貼る、というのをやると辺の数が最大になります。考えられる頂点のうち、すべての２頂点のセットをカバーしているので、これ以上辺を増やすと必ず閉路ができ、題意に合いません（閉路がダメ、というのはサンプルを見ないとよくわからず、少し意地悪ですが）。
　なんか説明が面倒になってきたので、写真でお茶を濁します

　1-(i+1)- ... -B
と行く行き方が2のi乗通りあるので、いらないのを削っていきます。

int main(){
    ifstream ifs("B-large-practice.in");
    ofstream ofs("op_a.txt");
    int test; ifs >> test;
    rep(casenum, test){
        ll B, M;
        ifs >> B >> M;
        ofs << "Case #" << casenum + 1 << ": ";
        if(M > (1LL << B - 2)){
            ofs << "IMPOSSIBLE" << endl;
            continue;
        }
        ofs << "POSSIBLE" << endl;
        vector<vector<int> > res(B, vector<int>(B, 0));
        if(M == (1LL << B - 2)){
            res[0][B - 1] = 1;
            M--;
        }
        for(int i = 1; i <= B - 2; i++){
            if(1LL & (M >> i - 1))
              res[0][i] = 1;
            res[i][B - 1] = 1;
            for(int j = 1; j < i; j++){
                res[i][j] = 1;
                res[j][B - 1] = 1;
            }
        }
        rep(i, B) rep(j, B){
            ofs << res[i][j];
            if(j == B - 1) ofs << endl;
        }
    }
    return 0;
}

　良問だと思いますが、僕には難しすぎました。
　Greedyしかないセットはダメですね。