yukicoder : No.2339 Factorial Paths

これは賢い。
https://yukicoder.me/problems/no/2339

問題

整数Nが与えられる。
以下のグリッドを構築せよ。

• 任意の幅W・高さHのグリッドを選択し、各マスの移動可・不可を定める。
• 左上角のマスから右下角のマスまで、右隣りまたは下隣りの移動可マスをたどって移動するときの経路がN!通りになるようにする。

解法

(A+1)×(B+1)の長方形のグリッドがあれば、Binom(A+B,B)=(A+B)!/(A!*B!)通りの経路が作れる。
これを活かし再帰的に考えよう。

L=floor(N/2)、R=ceil(N/2)とすると、N!=Binom(N,L)*L!*R!となる。
よって(L+1)*(R+1)の長方形グリッドの右下に、さらにL!通り及びR!通りの経路を持つ形状を再帰的に連結していけばよいことになる。

string S[2020];
int N;
int ty,tx;
const int MA=2000;

void dfs(int N) {
	if(N==1) return;
	int L=N/2;
	int R=N-L;
	
	int y,x;
	FOR(y,L+1) FOR(x,R+1) S[ty+y][tx+x]='.';
	ty+=L;
	tx+=R;
	dfs(L);
	dfs(R);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,MA) S[y]=string(MA,'#');
	
	dfs(N);
	for(x=tx;x<MA;x++) S[ty][x]='.';
	for(y=ty;y<MA;y++) S[y][MA-1]='.';
	cout<<MA<<" "<<MA<<endl;
	FOR(y,MA) cout<<S[y]<<endl;
	
	
}

まとめ

この方法だとサイズが一辺O(NlogN)かかって、かなり移動不可マスが多い。
移動不可マスを減らして一辺O(N)マスぐらいの方法ってあるかな。