Google Code Jam 2016 Round1C B Slides!
https://code.google.com/codejam/contest/4314486/dashboard#s=p1
全く分かりませんでした。というか、人間が解ける問題に見えませんでした。
1からBまでM通りの行き方があるグラフの隣接行列をつくれ、という問題。
こんな感じで、あるノードを付け足すごとに、すでにあったノードに全部に辺を貼る、というのをやると辺の数が最大になります。考えられる頂点のうち、すべての2頂点のセットをカバーしているので、これ以上辺を増やすと必ず閉路ができ、題意に合いません(閉路がダメ、というのはサンプルを見ないとよくわからず、少し意地悪ですが)。
なんか説明が面倒になってきたので、写真でお茶を濁します
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しかないセットはダメですね。