ABC056-D "No Need" 解説

#こんにちは
黄色Difficultyです。自力ACできて嬉しいので解説を書きます。
問題はこれ。
No Need
#概要

• $a_{1}$,$a_{2}$,...,$a_N$の$N$個の正の整数がある。
• その部分集合のうち総和が$K$以上の集合が「良い集合」。
• $a_{i}$を含む「良い集合」全てにおいて、そこから$a_{i}$を除いた集合も「良い集合」であるとき$a_{i}$は「不必要」。
• 「不必要」な数の個数を求めよ。

#制約

• ${1} \leq{N} \leq {5000}$
• ${1} \leq{K} \leq {5000}$
• ${1} \leq{a_i} \leq {10^9}$

#考えたこと
まず、制約から$O(NK)$が通ることがわかるので、$a_{i}$それぞれに対して個別に判定して良さそうです。しかし、問題文のまま愚直に判定したのでは、$a_i$を含む集合を全て列挙し、そこから$a_{i}$を除くという煩わしい操作をする必要があります。そこで、次のように問題文の言い換えをします。

• $a_{1}$,$a_{2}$,...,$a_N$の$N$個の正の整数がある。
• その部分集合のうち総和が$K$以上の集合が「良い集合」。
• $a_i$を含まない集合のうち総和が$K$未満のものを考える。この中で総和が最大の集合に$a_i$を足した時、$K$を超えれば$a_i$は「不必要」でない。
• 「不必要」な数の個数を求めよ。

なぜこの言い換えが成立するのか説明します。
問題概要の

• $a_{i}$を含む「良い集合」全てにおいて、そこから$a_{i}$を除いた集合も「良い集合」であるとき$a_{i}$は「不必要」。

の部分の対偶をとると、

• $a_{i}$が「不必要」でないとすると、$a_i$を含む「良い集合」のうち少なくとも1つは$a_i$を引くと「良い集合」ではなくなる。

となります。

集合の総和を考えたいとなると選んだカードとそこまでの総和を状態として持つDPをしたくなります。しかし、ここで注意すべきなのは「良い集合」とは総和がK以上の集合を指すことです。「K以上」となると集合の総和がDPの状態として持つことができない大きさになってしまいます。そこでもう一度言い換えをします。

• $a_i$を含まない集合のうち総和が$K$未満のものを考える。この中で総和が最大の集合に$a_i$を足した時、$K$を超えれば$a_i$は「不必要」でない。

上の

• $a_{i}$が「不必要」でないとすると、$a_i$を含む「良い集合」のうち少なくとも1つは$a_i$を引くと「良い集合」ではなくなる。

を判定するには総和が最大の集合だけ考えればよいというのが大切です。

こうなれば、 $a_i$それぞれに対して
$DP[j$番目まで$({1} \leq{j} \leq {N},i$は除く$)][$総和$k({1} \leq{k} \leq {K})]=true$ or $false$
という DPを考えることができます。しかしこれでは$O(N^2K)$となり、TLEしてしまいます。

そこで少し工夫をします。DPの配列を前からの総和で1つ、後ろからの総和で1つ持ち前計算をしておくのです。こうすれば$a_i$それぞれにおいて前からの総和、つまり$j$番目$({1} \leq {j} \leq {i-1})$を決め打ちし、後ろからのDPにおいて足して$K$を超えない最大のものを二分探索で求めることができるので、全体計算量は$O(NKlogK)$となりACできます。

#ACコード

main.cpp

#include <bits/stdc++.h>

#define int long long

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)a, i##_len=(b); i<i##_len; i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

#define all(box) box.begin(), box.end()

using namespace std;

using P = pair<int,int>;
using ll = long long;

const long long INF = LLONG_MAX/3;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

bool dp[5010][5010]={},dpr[5010][5010]={};
signed main(){
	int n,k;
	cin>>n>>k;
	int a[5010];
	rep(i,n){
		cin>>a[i];
	}
	dp[0][0]=true;
	dpr[0][0]=true;
	rep(i,1,n+1){
		rep(j,k)dp[i][j]=dp[i-1][j];
		rep(j,k){
			if(dp[i-1][j]){
				if(j+a[i-1]<k)dp[i][j+a[i-1]]=true;
			}
		}
	}
	rep(i,1,n+1){
		rep(j,k)dpr[i][j]=dpr[i-1][j];
		rep(j,k){
			if(dpr[i-1][j]){
				if(j+a[n-i]<k)dpr[i][j+a[n-i]]=true;
			}
		}
	}
	int cnt=0;
	rep(i,n){
		int mn=INF;
		vector<int> s,t;
		rep(j,k){
			if(dp[i][j])s.push_back(j);
			if(dpr[n-i-1][j])t.push_back(j);
		}
		rep(j,s.size()){
			int l=lower_bound(t.begin(),t.end(),k-s[j]-a[i])-t.begin();
			if(l<t.size())chmin(mn,s[j]+a[i]+t[l]);
		}
		if(mn==INF||mn-a[i]>=k)cnt++;
	}
	cout<<cnt<<endl;
}

#感想
初めて記事を書いてみましたが、自分の考えたことを文字に起こすのって案外難しいですね。わかりにくくなってしまったのは自覚していますが、なかなかうまい言い方が思いつきません。
公式解説を見る限り、もっと計算量を改善する方法があるようですが、僕には理解できませんでした。どなたか教えてくださると嬉しいです。