ABC156 E - Roaming

f:id:tkr987:20200617090846p:plain

https://atcoder.jp/contests/abc156/submissions/13470562

人の移動パターンは関係ないので意識してしまうと一生答えが出ない
移動すると空部屋が増える傾向にある→移動した人を部屋の外に集めて空部屋以外に再分配する重複組み合わせ $_nH_r$
どの部屋を空部屋にするか組み合わせ $_nC_r$
空部屋を固定して考え、最小個数の空部屋から最大個数の空部屋まで上記を計算した合計が答え

f:id:tkr987:20200617093035p:plain

文章を読んだとき、人が移動すると空部屋が増える傾向にある、ということに気づける。同じ移動数kでも移動パターンによって空部屋の数が変化するが、移動パターンは答えと関係ないので無駄なことは考えないこと。

具体的には、移動パターン関係なく空部屋の数を固定して考える。例えば、部屋が6個、空部屋が2個、移動2人、だった場合、組み合わせは「空部屋を2個選ぶ組み合わせ×2人以上いる部屋の組み合わせ」という考え方で $_6C_2 \times _4H_2$ になる。このとき、空部屋以外は1人以上いるはずなので $_4H_6$ と計算するのは不正解。また、1人だけの部屋は2人以上の部屋が決まれば確定するので計算不要。