Codeforces #228 Div1. B. Fox and Minimal path

本番アプローチは正しかったのに凡ミスしたもったいない問題。
http://codeforces.com/contest/388/problem/B

問題

最大1000ノードからなる無向辺グラフにおいて、１番の点から２番の点に至る最短経路の組み合わせ数がK個となるグラフを作成せよ。

解法

K<=10^9とかなり大きいので、まずは大きな数値を作る方法を考える。
1番の点から10～19番に辺を張り、10～19番から20～29番に10x10通り辺を張り、20～29番から30～39番に10x10通り辺を張り…とやっていくと、10倍10倍に最短経路の組み合わせを作ることができる。

そこで、上記繰り返しを0～8回行うような組み合わせをそれぞれ作っておけば、10^0～10^8の組み合わせを実現できる。
あとは、Kの10^i桁の値に対応して、10^i通りの組み合わせを実現できる点にその数だけパスを張ればよい。
以下のやり方では点を豪勢に使いすぎて10^9を処理できなかったため、Kから1引いて、その分別の場所に1本余分に辺を張っている。

なお、本番中に思いついたのは桁毎の処理だけど、同様にbit毎にも処理可能。
また、無駄な点を減らせば100ノードでもK<=10^9に対処できる。

ll K;
int mat[1001][1001];

void solve() {
	int f,i,j,k,l,x,y,rr=0;
	
	cin>>K;
	K--;
	FOR(i,9) {
		FOR(j,(i==0) + K%10) mat[0][2+100*i+j]=1;
		FOR(j,9) {
			FOR(x,10) FOR(y,10) {
				if(j>=i && y!=0) continue;
				mat[2+100*i+j*10+x][2+100*i+j*10+10+y]=1;
			}
		}
		FOR(x,10) if(2+100*i+9*10+x<1000) mat[2+100*i+9*10+x][1]=1;
		K/=10;
	}
	
	
	_P("1000\n");
	FOR(y,1000) {
		FOR(x,1000) _P((mat[y][x] || mat[x][y])?"Y":"N");
		_P("\n");
	}
}

まとめ

本番は10^9の時に1002ノード目を参照してしまいミス…。