kmjp's blog

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

yukicoder : No.660 家を通り過ぎないランダムウォーク問題

先日のAGCを見てなかったら解けなかった。
https://yukicoder.me/problems/no/660

問題

1次元の数直線上で初期位置が0の位置にいる。
1秒毎に+1か-1いずれかの相対位置の点に移動する。

  1. Nの点に到達すると、以降の移動を止める。

2N秒以内に+Nの点にたどり着く移動順の組み合わせを求めよ。

解法

この条件は以下のように考えることができる。
k+1手目で始めて+Nの点に到達するための条件は

  • k手目で(N-1)の点にいる
  • k手目までには+Nの点に触れない

である。
k手目で(N-1)の点にいるには、-1の移動を(k-(N-1))/2回、+1の移動を(N-1)+(k-(N-1))/2回行うことに相当する。
さて、前者をA回、後者をB回行うことを考える。
条件の2つめを無視すると、この手順は(0,0)からX軸またはY軸にそって1ずつ移動し、(A,B)に移動することに相当する。
ただしY軸の移動回数がX軸の移動階数をN回以上上回ってはいけない。

…この問題はカタラン数の応用でCombination計算2回で解け、ちょうど前回のAGCのE問題の解説が参考となる。
あとはkを総当たりしていこう。

int N;
ll mo=1000000007;

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	ll pat=0;
	for(i=N-1;i<=2*N-1;i++) if((i-(N-1))%2==0) {
		x=(i-(N-1))/2;
		y=(N-1)+x;
		pat+=combi(x+y,x)-combi(x+y,y+1);
	}
	cout<<(pat%mo+mo)%mo<<endl;
}

まとめ

カタラン数苦手だったけど前回のAGCとこれで少しは苦手意識が薄れたかも。