きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 132:D - Blue and Red Balls

問題

https://atcoder.jp/contests/abc132/tasks/abc132_d

解法

i 回操作が必要なとき,青玉が連続している区間が i 個あるということなので,(N - K) 個ある赤玉の間と左端と右端の (N - K + 1) 個の隙間に青玉の区間を i 個当てはめればよい.これは C(N - K + 1, i) 通りある.また,i 個ある青玉の区間のそれぞれに何個青玉を割りふるかを考える.各区間につき最低 1 個は割り当てないといけないので (K - i) 個の青玉を i 個の区間に当てはめればよい.これは C(K - i + (i - 1), i - 1) = C(K - 1, i - 1) 通りある.この 2 つの通り数を掛け合わせたものが答えになる.前処理でコンビネーション計算をする必要がある.O(N + K).

解答

https://atcoder.jp/contests/abc132/submissions/6351749

f:id:babcs2035:20190713135713p:plain