ARC070 D - No Need
解説
wa = a_iを含む良い集合の和の最小値とすると、
wa - a_i ≧ K <=> a_i は不必要
wa - a_i < K <=> a_i は必要
となる。
全てのカードiについて、カードiを含まないカードで作れる和をdpで調べる。
dp[j][k] = カードjまで調べたときに和kを作れるかどうかとする。
wa は (dp[j][k] = trueかつk≧K-a_i) となる最小のk + a_iである。
カードの数は最大109だが、K以上の数をKとしても必要かどうかの判定には影響しないので計算量はO(NK)となる。
よって全体でO(N2 K)で部分点が取れる。
満点解法は、カードiが不必要ならa_i ≧ a_jであるカードjも不必要であることを用いる。
aをソートしておいて、不必要なカードと必要なカードの境界を二分探索で求めれば良い。
計算量はO(NKlogN)となる。
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #include <deque> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int N, K; vector<int> a; bool dp[5050][5050]; // 不必要ならtrue bool calc(int i) { vector<int> b; FOR(j,0,N) if(i != j) b.push_back(a[j]); CLR(dp); dp[0][0] = true; FOR(j,0,N-1) { FOR(k,0,K+1) { if(!dp[j][k]) continue; // b[j]を使う if(k+b[j] <= K) dp[j+1][k+b[j]] = true; // b[j]を使わない dp[j+1][k] = true; } } int wa = 0; FOR(j,0,K+1) { if(dp[N-1][j]) { wa = a[i] + j; if(wa >= K) break; } } return (wa < K) || (wa - a[i] >= K); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> K; a.resize(N); FOR(i,0,N) { int in; cin >> in; in = min(in, K); a[i] = in; } sort(a.begin(), a.end()); int l = -1, r = N + 1; while(r - l > 1) { int m = (r + l) / 2; if(calc(m)) l = m; else r = m; } cout << min(r, N) << endl; return 0; }
コメント
部分点はできたが、二分探索に気づけなかった。