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も使えそう。