yukicoder : No.332 数列をプレゼントに

お疲れ様でした。
http://yukicoder.me/problems/894

問題

N個の整数列A[i]が与えられる。
この部分列で総和がXとなるものが存在するならそれを答えよ。

なお、Aの全数値の積は10^100以下である。

解法

A,Xの上限は大きいため、一般的なDPによるナップサック解法では間に合わない。
そこで最後の条件に着目しよう。
この積の条件から、Aのうち大きな数値の登場回数はかなり限定的であることがわかる。
例えば10^5以上の数値は20個以下しか登場しえない。

そこで、Aが小さなうちはDPし、残りの大きないくつかのAについてはBitDPの要領で総当たりするとよい。
ちょっと変則的な半分全列挙と言えるね。

ll N,X;
pair<int,int> P[101];
ll A[101];

int dp[220000];
char ok[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) cin>>P[i].first, P[i].second=i, ok[i]='x';
	sort(P,P+N);
	FOR(i,N) A[i]=P[i].first;
	
	ll sum=0;
	MINUS(dp);
	dp[0]=0;
	
	FOR(i,N) {
		if(sum+A[i]>=200000) break;
		for(j=sum;j>=0;j--) if(dp[j]>=0 && dp[j+A[i]]==-1) dp[j+A[i]]=i;
		sum+=A[i];
	}
	
	assert(N-i<=25);
	int low=i;
	for(int mask=0;mask<1<<(N-low);mask++) {
		ll t=0;
		FOR(i,N-low) if(mask&(1<<i)) t+=A[i+low];
		if(X-t<0 || X-t>200000) continue;
		
		if(dp[X-t]>=0) { 
			FOR(i,N-low) if(mask&(1<<i)) ok[P[i+low].second]='o';
			x=X-t;
			while(x) ok[P[dp[x]].second]='o', x-=A[dp[x]];
			return _P("%s\n",ok);
		}
	}
	_P("No\n");
	
}

まとめ

25日間フル参加の副作用として、生活のリズムがちょっと整った。
（幸い大半の問題は1時間以内で解けたので、余計にリズムを崩す要因にならずにすんだ）