ARC104 D - Multiset Mean (700)
最初の考察
愚直にDPを考えると$ dp[i個目まで見て][j個選んで][和がl] になるが$ O(N^4k^2)でMLEしそう
$ NK個を分割する場合の数を計算して長さ$ N+1以上の場合を全て引けば計算できそう
引く部分の計算が結局大変
次の考察
$ 2x \le nとしてx未満とxより大きい数の2種類に分類するとそれらが打ち消せるように作れる最大の数は$ \frac{kx(x-1)}{2}
$ 2x \gt nなら$ x = n - xとしておく
更にxの個数を独立に選べるので$ k+1を掛けて最後に全体から1を引く
1引くのは両方が空の場合を引いている
答えは単純にこれになるのでは?
同じ数でも違うパターンで作れるので駄目
最終的な考察
$ dp[i][j] でi以下の数だけ使ってjを作れるパターンとする
iの小さい方から作っていく
i以下の場合を求めるときのi-1の場合の遷移元は$ O(K)通りになるので累積和で計算量を減らす
累積和はi個飛ばしの和を求める
DPの計算とx毎の答えの計算が両方とも$ O(N^3K)になるので間に合う