AtCoder Regular Contest 070D: No Need

http://arc070.contest.atcoder.jp/tasks/arc070_b

なんとなくの解法ならすぐわかったけど、それを詰めるのがつらかった。

0~i-1の和をsum[i]と表す。

aをsortしてai~aNの要素のうちいくつかを選んで和を作る。その内、Kを超えないもので最大の値をJとする。
すると
iより小さい要素が不要<=> (J+sum[i] < K)かつ(和のうちK以上のものが存在)
が成立する。この証明は割と簡単にできる。

int N, K;

int A[5010];
bool dp[5010][5010];
ll S[5010];

void solve() {
	cin >> N >> K;
	rep(i, 0, N) {
		cin >> A[i];
	}
	sort(A, A + N);
	rep(i, 0, N) {
		S[i + 1] = A[i];
		S[i + 1] += S[i];
	}
	dp[N][0] = true;
	for(int i = N - 1; i >= 0; i--) {
		int a = -1, b = -1;
		for(int j = 0; j <= K; j++) {
			if(j - A[i] >= 0) dp[i][j] = max(dp[i][j], dp[i + 1][j - A[i]]);
			dp[i][j] = max(dp[i][j], dp[i + 1][j]);
			if(dp[i + 1][j] && j < K) a = j;
			if(dp[i][j] && j < K) b = j;
		}
		if(K - a <= A[i]) dp[i][K] = true;
		if(dp[i][K] && b + S[i] < K && i != 0 && A[i] != A[i - 1]) {
			cout << i << "\n";
			return;
		}
	}
	if(!dp[0][K]) cout << N << "\n";
	else cout << "0\n";
}

これはオーバーキルで、以下のもっと簡単な考察で満点が取れた。
単にa0-a(i-1)の和の集合とa(i+1)~a(N-1)の和の集合を前もって計算しておけば各iについてO(K)で判定できるので全体の計算量はO(NK)となる。

戻すdpも使えそう。