先日のAGCを見てなかったら解けなかった。
https://yukicoder.me/problems/no/660
問題
1次元の数直線上で初期位置が0の位置にいる。
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とこれで少しは苦手意識が薄れたかも。