マスターオブ場合の数を競プロで殴る その2「ヒツジ vs オオカミ」
企画の説明は 第1回のエントリー をご覧ください。
問題
オオカミとヒツジがそれぞれ $N$ 匹います。あなたの仕事はこれらの $2N$ 匹を $1$ つのオリの中に入れることです。注意すべきこととして、オリの中に $1$ 匹以上のヒツジがいるとき、オオカミの数がヒツジの数を上回ると、ヒツジは食べられてしまいます。ヒツジが食べられないように、この $2N$ 匹を $1$ 匹ずつすべてオリの中に入れる方法は、何通りありますか？ ただし、オオカミ $N$ 匹は区別せず、ヒツジ $N$ 匹も区別しません。
答えを $998244353$ で割ったあまりを求めてください。
制約
- $1 \leq N \leq 2 \times 10 ^ {5}$
『マスター・オブ・場合の数』P.12 §1-3. をもとに改題
例えば $N = 3$ のとき、ヒオヒヒオオ（ヒ＝ヒツジ、オ＝オオカミ）はOKですが、ヒヒオオオヒはNGです（5匹目の時点でヒツジ2匹に対してオオカミ3匹になるので食べられてしまう）。
クリックで解答を表示
解答
基本的に $($ ヒツジの頭数 $)-($ オオカミの頭数 $)$ がマイナスになった瞬間アウトなのですが、一つだけ例外があり、ヒツジが $\mathbf{0}$ 匹のときはオオカミを入れても $\mathbf{1}$ 匹までなら耐えます（ $2$ 匹以上入れるとヒツジを入れられなくなって詰む）。
このことに注意しつつ、横軸に時間、縦軸に $($ ヒツジの頭数 $)-($ オオカミの頭数 $)$ を取ったグラフを書くと、下図のようになります（下図は $N=3$ の場合）。
赤い線を踏んだ瞬間ゲームオーバーです。この図で赤い線を通らずにスタートからゴールへ向かう道順の個数を数えます。DPをすれば $O(N^{2})$ で解けますが、今回の制約では間に合いません。
上述した「例外」を表す緑色の線が出しゃばっていてどう見ても厄介なので、ひとまず緑色の道を通らない場合を考えてみましょう。
この経路数は有名問題で、カタラン数 $c_N$ になります。
カタラン数
$n$ 番目のカタラン数を $c_n$ とすると、
$$c_n = {}_{2n}\mathrm{C}_{n} - {}_{2n}\mathrm{C}_{n - 1}$$
なぜこの経路数がカタラン数になるのかについては、インターネット上に様々な解説がありますので、ググったりして自分に合うものを探してみてください。個人的オススメをいくつか貼っておきます。
えびまさんの解説動画（カタラン数の話は1:10～3:00）
さて、本筋に戻ります。先程は緑色の道を無視した道順を考えたので、次は緑色の道を通る道順を考えます。
緑色の道を通り抜けると、スタートの $1$ つ右の地点に出て来ます。ここで、この地点からもう行けない道は消してしまいましょう。すると……
先程と同じ図が $1$ マス縮小されて出てきました！ よって、緑色の道を通る場合は $c_{N-1}$ 通りになります。
以上より、緑色の道を通る場合と通らない場合をあわせて $c_{N} + c_{N - 1}$ 通りが求める答えです。
実装例
from functools import reduce MOD = 998244353 # nCrを求める関数 def comb(n, r): if not 0 <= r <= n: return 0 if r == 0 or r == n: return 1 numer = reduce(lambda x, y: x * y % MOD, (n - r + k + 1 for k in range(r))) denom = reduce(lambda x, y: x * y % MOD, (k + 1 for k in range(r))) return numer * pow(denom, MOD - 2, MOD) % MOD # n番目のカタラン数を求める関数 def catalan(n): return (comb(2 * n, n) - comb(2 * n, n - 1)) % MOD n = int(input()) print((catalan(n) + catalan(n - 1)) % MOD)
余談
競プロにおいては、括弧列の問題で同様の考え方が役立つようです。$N$ 組の括弧を正しく並べて括弧列にする方法の個数は、まさにカタラン数 $c_N$ 通りです。流石にそれを直接問う問題は少ないですが、今回のように道順問題っぽい図を書いて考えるのは括弧列問題において定石の一つみたいです。
