ABC178 D - Redistribution (400)
それぞれの長さの数列でいくつ作れるかを求めてそれを足し合わせる
最大の配列の長さは
$ \frac{S}{3}
長さ
$ i
の配列の場合、自由に配置できるのは
$ S - 3i
個
$ i-1
個の仕切りを加えて
$ i-1
個を選ぶのと等しいのでこの場合の場合の数は
$ _{S-2i-1}C_{i-1}
組み合わせを求めるための前準備も全ての長さで組み合わせを求めるのも
$ O(S)
問題:
https://atcoder.jp/contests/abc178/tasks/abc178_d
提出:
https://atcoder.jp/contests/abc178/submissions/16694358
#ABC178
#400pt
#D
#ABC
#AtCoder
#O(N)
#順列組み合わせ