読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces #404 D. Anton and School - 2

http://codeforces.com/contest/785/problem/D

解法

一番右にある'('の位置を固定したとき、条件を満たす括弧列がいくつあるかを数える。

f:id:pekempey:20170316191116p:plain

固定した左側に'('が4個、右側に')'が5個ある。

f:id:pekempey:20170316191528p:plain

条件を満たす括弧列を作るには、左側の領域から'('を k 個取ったら、右側の領域から')'を k+1 個とればいい。

つまり、パターン数は以下の通り。

\[ \binom{4}{0}\binom{5}{1}+\binom{4}{1}\binom{5}{2}+\binom{4}{2}\binom{5}{3}+\binom{4}{3}\binom{5}{4}+\binom{4}{4}\binom{5}{5} \]

一般に、左側の領域に'('が L 個、右側の領域に')'が R 個ある場合、パターン数は以下の式となる。

\[ \sum_{k=0}^{\infty} \binom{L}{k}\binom{R}{k+1} \]

細かいことは気にせず無限大まで飛ばした。\(\binom{n}{r}=\binom{n}{n-r}\) であることを使うと以下の式に変形できることが分かる。

\[ \sum_{k=0}^{\infty} \binom{L}{k}\binom{R}{R - k - 1} \]

二項係数の下側の値、ここでは \(k\) と \(R - k - 1\) であるが、その和は 一定になっていて \(R - 1\) である。つまり、これは畳み込みになっている。

多項式 \( (1+x)^L (1+x)^R \) の \(x^{R-1}\) の係数がちょうどの畳み込みの値と一致するはずなので、

\[ \sum_{k=0}^{\infty} \binom{L}{k}\binom{R}{R - k - 1}=\binom{L+R}{R - 1} \]

である。よってこの問題を解くことができた。

補足

母関数による証明はやや技巧的に感じるかもしれないので、簡単な証明も書いておく。

男が N 人、女が M 人いる。合計 N+M 人から K 人選ぶ方法は C(N+M, K)通りある。男から x 人選び、女から K-x 人選ぶ方法数は C(N, x)C(M, K-x) 通りある。xを0からKまで動かして総和を取ればN+M 人から K 人選ぶ方法数と一致する。