Codeforces 388(#228 Div1) B. Fox and Minimal path

問題

無向グラフで頂点1から2への最短パスの総数がちょうどk通りであるような頂点数1000以下のグラフを出力せよ。
答えが複数ある場合はどれを出力してもよい。

制約条件

解の存在は保証されている。

方針

発想としては、kを二進法で書いて、i桁目が1のとき、
2つに分かれて合流する道をi個くっつけた道をスタートからゴールにひく（合計の長さは一定になるように後ろに適当に一本道をくっつける）
というのをやればいいだけ。

これだと頂点が2000くらいになってしまうので、
一番大きい桁だけ分かれて合流するのを繰り返す道を作って、
残りのそれより小さい1の桁は、
（分かれ道の途中に長さの帳尻を合わせて）一本道で途中に合流するとかやればいい。

int k;
string g[1000];

int main(){
	cin >> k;
	int n = 1000;
	rep(i, n) g[i] = string(n, 'N');
	
	int p = 2, pos;
	rep(i, 32) if(k >> i & 1) pos = i;
	{
		int prev = 0;
		rep(j, pos){
			g[prev][p] = g[p][prev] = 'Y'; p++;
			g[prev][p] = g[p][prev] = 'Y'; p++;
			g[p - 1][p] = g[p][p - 1] = 'Y';
			g[p - 2][p] = g[p][p - 2] = 'Y';
			prev = p++;
		}
		rep(j, 2 * (32 - pos)){
			int next = j == 2 * (32 - pos) - 1 ? 1 : p++;
			g[prev][next] = g[next][prev] = 'Y';
			prev = next;
		}
	}
	
	rep(i, pos) if(k >> i & 1){
		int prev = 0;
		int goal = 3 * (pos - i) + 1;
		
		rep(j, 2 * (pos - i)){
			int next = j == 2 * (pos - i) - 1 ? goal : p++;
			g[prev][next] = g[next][prev] = 'Y';
			prev = next;
		}
	}
	cout << n << endl;
	rep(i, n) cout << g[i] << endl;
	return 0;
}