かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC205 E - White and Black Balls

ABC 数え上げ 競技プログラミング 解説

問題はこちら

問題概要

白いボール{N}個と黒いボール{M}個を一列に並べるとき，各{i(1\leq i\leq N+M)}について左から{i}個のボールのうち白いものの個数を{w_i}，黒いものの個数を{b_i}とおいたとき，すべての{i}について{w_i\leq b_i +K}が成り立つような並べ方の数を求めよ．

{1\leq N,M\leq 10^6\\ 1\leq N+M\\ 0\leq K\leq N}

解説

結局問題は，左からボールを，白のボールの数が黒のボールの数{+K}より大きくならないように置いていく方法の数を数える必要があります．

これは以下のようなグリッド上で左上から右下までの最短経路の数と等しいです．ただし，左に行くというのは白のボールを置くこと，右に行くというのは黒のボールを置くことに対応します．×のところは通れません．

{N=4,M=3,K=2}の例

f:id:kanpurin:20210613222004p:plain:w400

これはかなり難しそうですが，階段状の最短経路についていろいろ調べるとこんなのが出てきます．これを用いると，「青丸から赤丸への最短経路数」から「青丸から緑丸への最短経路数」を引いたものが答えとなります．

f:id:kanpurin:20210613223742p:plain:w400

答えは{\displaystyle\binom{N+M}{N}-\binom{N+M}{N-K-1}}．ただし，{N>M+K}ならそもそも到達できないので{0}

kanpurin.hatenablog.com

提出プログラム

https://atcoder.jp/contests/abc205/submissions/23442405

感想

検索なしだと思いつかなかった．実際はカタラン数っぽかったのでカタラン数で検索してたら導出見つけました．