問題リンク
問題概要
n個の部屋に1人ずつ人がいる。
「ある部屋から1人、別の部屋に移動する」という操作がちょうどk回行われた後の人数の組み合わせとしてありえるのは何通りか。
解法
\(n\geqq3\)なので無駄打ちが可能。
たとえば部屋1→部屋2と移動するところを、同じ人が部屋1→部屋2→部屋3と考えると実質同じ結果で操作回数を増やすことができる。
したがって、「ちょうどk回」は「k回以下」と読みかえて良くなる。
以下、「m-1回では不可能かつちょうどm回で可能」な部屋の人数の組み合わせを考える。
これは、「n-m個の部屋にそれぞれ1人以上、m個の部屋は空」となるものの全体である。m個の部屋が空なので明らかにm-1回では不可能で、空の部屋に元々いたm人を無駄なく移動させるとm回で可能なのもわかる。
このようなものの総数は
「n個の部屋のうちn-k個を選ぶ組み合わせの総数」×
「n-k個の部屋に1人以上、合計でn人を入れる組み合わせの総数」なので、
\( {}_n C_{n-k} \times\) \( {}_{n-1} C_{n - k - 1} \)
となる。
提出
https://atcoder.jp/contests/abc156/submissions/10278980
感想
ちょっと複雑で頭の整理に時間がかかった。
