AtCoder ARC #070 : D - No Need

ARCとはいえ、久々に1ページ目。
http://arc070.contest.atcoder.jp/tasks/arc070_b

問題

N枚のカードがあり、それぞれ整数値A[i]が書かれている。
カードの部分集合における値の総和がK以上である時、その部分集合は「良い」と定義する。

あるカードが不必要であるとは、以下を意味する。

• 「そのカードを含むすべての良い部分集合において、それぞれそのカードを除いても、やはり良い部分集合のままである」

不必要なカードは何枚あるか。

解法

想定解法とはちょっと違う解法。

不必要な条件を言い換えると、i番のカードを含む合計K以上となるカード集合の∈が、いずれもi番のカードを除いてもK以上を維持できるということは、結局i番のカードを除いたとき、総和が[K-A[i],K-1]となる部分集合が存在しないことに相当する。

よって、あとはカードiに対し、他のカードで総和が[K-A[i],K-1]となる部分集合が存在するかどうかを判定すればよい。
戻すDPで行う手もあるが、自分は別のDPで対応した。まず以下のDPをO(NK)で行う。

• L(i,x) := カード[0,i]の部分集合で合計xとなるものが存在するか
• R(i,x) := カード[i,(N-1)]の部分集合で合計xとなるものが存在するか

このDPの結果を用いると、各iに対し、L(i-1,x)かつR(i+1,y)かつ(x+y)が[K-A[i],K-1]に含まれる、というようなx,yが存在しないかを示せばよくなる。
xを固定すると、結局y∈[K-A[i]-x, K-1-x]に対しR(i+1,y)=Trueとなるものを探すことになる。
xを1動かすごとに[K-A[i]-x, K-1-x]は1ずつ動くので、尺取り法の要領でR(i+1,y)がTrueとなるyの存在を探そう。

int N,K;
int A[5050];
bitset<8192> L[5050],R[5050];
ll LT[5050],RT[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	L[0][0]=1;
	R[N+1][0]=1;
	FOR(i,N) {
		bitset<8192> T=L[i];
		T<<=A[i];
		L[i+1]=L[i] | T;
		if(L[i].count() != T.count()) L[i+1][8191]=1;
		LT[i+1]=LT[i]+A[i];
	}
	for(i=N-1;i>=0;i--) {
		bitset<8192> T=R[i+2];
		T<<=A[i];
		R[i+1]=R[i+2] | T;
		if(R[i+2].count() != T.count()) R[i+1][8191]=1;
		RT[i+1]=RT[i+2]+A[i];
	}
	
	int ret=0;
	FOR(i,N) {
		ll LB=max(0,K-A[i]);
		ll RB=K-1;
		deque<int> AA,BB;
		FOR(x,8192) if(R[i+2][x]) AA.push_back(x);
		
		int hoge=1;
		FOR(x,8192) if(L[i][x]) {
			ll LB2=LB-x,RB2=RB-x;
			while(AA.size() && AA.back()>=LB2) BB.push_front(AA.back()),AA.pop_back();
			while(BB.size() && BB.back()>RB2) BB.pop_back();
			if(BB.size()) {
				hoge=0;
				break;
			}
		}
		
		ret+=hoge;
		
		
	}
	
	cout<<ret<<endl;
}

まとめ

N,Kが意外に大きいのなんでだろうな。