Codeforces ECR #032 : E. Maximum Subsequence

ギリギリ全完。
http://codeforces.com/contest/888/problem/E

問題

N個の整数A[i]が与えられる。
これらの部分集合のうち、総和をMで割った余りの最大値を求めよ。

解法

A[i]やMは大きいので普通のナップサック解法は取れない。
Nが小さいので半分全列挙してしまおう。

前半N/2個の部分集合の総和がvの時、後半の部分集合の総和のうち(M-1)-vに近い値を取ればよい。

int N;
ll M,A[101];

vector<ll> X;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	N=35;
	
	for(int mask=0;mask<1<<18;mask++) {
		ll tot=0;
		FOR(i,18) if(mask&(1<<i)) tot+=A[i];
		X.push_back(tot%M);
		X.push_back(tot%M+M);
	}
	sort(ALL(X));
	
	ll ret=0;
	for(int mask=0;mask<1<<17;mask++) {
		ll tot=0;
		FOR(i,17) if(mask&(1<<i)) tot+=A[18+i];
		tot%=M;
		x = lower_bound(ALL(X),2*M-tot)-X.begin();
		ret=max(ret,(tot+X[x-1])%M);
		
	}
	
	
	
	cout<<ret<<endl;
	
	
}

まとめ

これはNの大きさで半分全列挙解がバレバレだな。