Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}