kyuridenamida さんの問題
問題 : -平-均-
ものすごくJOI 本選に出そうな問題だった.
部分点1 が$n \leqq 20$
部分点2 が$n \leqq 50,\ a_i \leqq 100,\ T \leqq 100$
満点が問題文の通り, みたいな感じ.
解法 :
比較的すぐに個数を数える感じのナップサック系DP であることは分かる.
$dp[i][j] :=$ $i$ 番目までの数で和を$j$ にする方法の総数, とすると, dp テーブルは空間計算量が$O(n^2T)$ くらいで, 時間計算量が$O(n^3T)$ となってしまうが, $\displaystyle \sum_{i=1}^{n} dp[i][T \times i]$ で答えが求まる.
ここで, ある部分数列$B$ 内の平均が$m $ だった時の事を考えると, この数列内の全ての数から$x$ を引くと平均は$m - x$ になる. これを利用して, 与えられた数列の数すべてから$T$ を引くと, 平均を$0$ にする問題になるが, これはいくつかの数を選んで$0$ を作る方法を聞いているので, $O(n^2T)$ 時間で計算することが出来る.
コード :
#include <cstdio> using namespace std; int dp[400010]; int main() { int a[128]; int n, T; scanf("%d %d", &n, &T); for (int i = 0; i < n; i++){ scanf("%d", a + i); a[i] -= T; } dp[200000] = 1; for (int i = 0; i < n; i++){ if (a[i] < 0) for (int j = 200000 + a[i]; j >= -200000; j--) dp[200000 + j - a[i]] = (dp[200000 + j - a[i]] + dp[200000 + j]) % 1000000009; else for (int j = -200000 + a[i]; j <= 200000; j++) dp[200000 + j - a[i]] = (dp[200000 + j - a[i]] + dp[200000 + j]) % 1000000009; } printf("%d\n", (dp[200000] + 1000000008) % 1000000009); return (0); }