問題はこちら
問題概要
白いボール
個と黒いボール
個を一列に並べるとき，各
について左から
個のボールのうち白いものの個数を
，黒いものの個数を
とおいたとき，すべての
について
が成り立つような並べ方の数を求めよ．
解説
結局問題は，左からボールを，白のボールの数が黒のボールの数
より大きくならないように置いていく方法の数を数える必要があります．
これは以下のようなグリッド上で左上から右下までの最短経路の数と等しいです．ただし，左に行くというのは白のボールを置くこと，右に行くというのは黒のボールを置くことに対応します．×のところは通れません．
の例
これはかなり難しそうですが，階段状の最短経路についていろいろ調べるとこんなのが出てきます．これを用いると，「青丸から赤丸への最短経路数」から「青丸から緑丸への最短経路数」を引いたものが答えとなります．
答えは
．ただし，
ならそもそも到達できないので
kanpurin.hatenablog.com
提出プログラム
https://atcoder.jp/contests/abc205/submissions/23442405感想
検索なしだと思いつかなかった．実際はカタラン数っぽかったのでカタラン数で検索してたら導出見つけました．
