ARC 070 D - No Need - kurarrr's memooo

問題

問題概要

N個の自然数a[i] (1<=i<=N)と自然数Kが与えられる。
その組み合わせからなる2^Nの集合を考え、そのうち部分和がKを超えるものを良い集合とする。
a[i]を含む任意の良い集合Aに対し、A\ {a[i]}(Aからa[i]を除いた集合)も良い集合であるならばa[i]は不必要であるとする。
a[i] (1<=i<=N)のうち、不必要な自然数の個数を求めよ。
1<=N,K<=5*10³,1<=a[i]<=10⁹(部分点解法は1<=N,K<=400)

解法

まず、a[i]>=Kならばa[i]は必要であるため、1<=a[i]<Kなるa[i]についてのみ考えれば良い。
よって1<=a[i]<=5*10³となる。
不必要の定義は次のように言い換えられる。「a[i]を除いた部分和でK-a[i]<=sum<Kなるものが存在するならa[i]は不必要でない」

部分点解法から。
dp[i][sum] := (iを除いて部分和sumを作れるか)として、iを除いた時の部分和を列挙していく。 for(k:K+1->0) for(j!=i) dp[i][k]] |= dp[i][k-a[j]] という漸化式に従う。
各iについて計算するとO(N³)となる。

a[i] >= a[j] でa[i]が不必要ならばa[j]も不必要であるという関係が成り立つことに注意すると、二分探索できることがわかる。
O(N²*logN)になり、間に合う。

また、 dp1[i][sum] := (a[j] (1<=j<=i)までの部分和でsumが作れるか)
dp2[i][sum] := (a[j] (i<=j<=N) ..)
として各DPを計算しておく。
a[j] (1<=j<i)の部分和x、a[j] (i<j<=N)の部分和yとして、各iについてxが作れるならば、K-a[i] <= x+y < Kなるyが取れれば条件を満たすため、 K-a[i]-y <= y < K-xを満たすyが存在するかを判定すれば良い。yに関する累積和を作っておけばこれはO(K)で判定できる。よって全体でO(NK)=O(N²)で解けることになる。

メモ

k:0->K+1とすると0->a[j]->2*a[j]とtrueになっていってしまう。(よくやるミス) そうならないためにはもう一次元増やすか、bitsetでやると良い。
最速解法見てるとO(NlogN)で解けてるっぽいんだけど全然わからん。

コード

部分点

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 5003;
const ll lmod = 1e9+7;

int N,K,a[MAX_N];
bool dp[MAX_N][MAX_N*2];

int main(){
  scanf("%d%d",&N,&K);
  int temp = 0;
  rep(i,N){
    int b;
    scanf("%d",&b);
    if(b<K) a[temp++] = b;
  }
  N = temp;
  fill(dp[0],dp[MAX_N-1],false);
  rep(i,N) dp[i][0] = true;
  int ans = 0;
  rep(i,N){
    rep(j,N){
      if(j==i) continue;
      for(int k=K+1; k>=a[j]; k--){
        dp[i][k] |= dp[i][k-a[j]];
      }
    }
    bool need = false;
    REP(j,K-a[i],K) need |= (dp[i][j]);
    if(!need) ans++;
  }
  cout << ans << endl;
  return 0;
}

満点

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 5003;
const ll lmod = 1e9+7;

int N,K,a[MAX_N];
bool dp[MAX_N*2];

int main(){
  scanf("%d%d",&N,&K);
  int temp = 0;
  a[temp++] = 0; //dummy
  rep(i,N){
    int b;
    scanf("%d",&b);
    if(b<K) a[temp++] = b;
  }
  N = temp;
  sort(a,a+N);
  a[N] = K; //dummy
  int l = 0,r = N+1,mid;
  while(abs(r-l)>1){
    mid = (l+r)/2;
    fill(dp,dp+K,false);
    dp[0] = true;
    rep(j,N){
      if(j==mid) continue;
      for(int k=K; k>=a[j]; k--){
        dp[k] |= dp[k-a[j]];
      }
    }
    bool need = false;
    REP(j,K-a[mid],K) need |= (dp[j]);
    if(!need) l = mid;
    else r = mid;
  }
  cout << l << endl;
  return 0;
}