kmjp's blog

競技プログラミング参加記です

Google Code Jam 2016 Round1C : B. Slides!

Codeforcesで似たようなの見たからなぁ…。
https://code.google.com/codejam/contest/4314486/dashboard#s=p1&a=0

問題

1~BのB個の頂点からなる有向グラフを考える。
1からBに至る経路が計M通りになるものを構築せよ。
ただし同じ2頂点間に複数の辺を張ってはならない。

解法

1≦i≦j≦B-1となる頂点対(i,j)の間にi→jという辺を張ろう。
すると頂点1から頂点iに至る経路は2^(i-2)通りできる。(i=1の時は1通り)

あとは各頂点からBに辺を張り、計M個の経路ができるようにしたい。
貪欲に頂点iを(B-1)から順に走査し、2^(i-2)≦Mならi→Bに辺を張りM -= 2^(i-2)で更新すればよい。
Mが大きすぎる場合、全頂点からBに辺を張っても計M通りに満たないので、その場合IMPOSSIBLEとなる。

int B;
ll M;
int mat[60][60];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>B>>M;
	ZERO(mat);
	for(x=0;x<B-1;x++) for(y=x+1;y<B-1;y++) mat[x][y]=1;
	for(y=B-2;y>=0;y--) {
		ll v=(y==0)?1:(1LL<<y-1);
		if(M>=v) mat[y][B-1]=1, M-=v;
	}
	
	if(M==0) {
		_P("Case #%d: POSSIBLE\n",_loop);
		FOR(y,B) {
			FOR(x,B) _P("%d",mat[y][x]);
			_P("\n");
		}
	}
	else {
		_P("Case #%d: IMPOSSIBLE\n",_loop);
	}
	
	
}

まとめ

これは既出っぽいな…。