7K12 blog

猫でも分かるアルゴリズム解説

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人以上の部屋が決まれば確定するので計算不要。

移動回数k回のとき、空き部屋の個数iは[0, min(n-1, k)]の範囲になる。この範囲に対して rep(i, 0, min(n, k + 1)) ans += count.C(n, i) * count.H(n - i, i); を計算すると答えになる。計算量は  O(N)