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である。

カードの数は最大10⁹だが、K以上の数をKとしても必要かどうかの判定には影響しないので計算量はO(NK)となる。

よって全体でO(N² 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;
}

コメント

部分点はできたが、二分探索に気づけなかった。