Codeforces ECR #021 : E. Selling Souvenirs

かなりゴリ押してしまった。
http://codeforces.com/contest/808/problem/E

問題

N要素の荷物があり、それぞれ重さはW[i]、価値はC[i]である。
重さの総和がMを超えない範囲で荷物のsubsetを求め、価値の総和を最大化せよ。

解法

単なるナップサック問題だが、重さの種類が3つしかないのが特徴的。

いくつか方法があり、O(N)やO(NlogN)解法もあるが、ここではO(N^2)ゴリ押し解法を紹介。
重さが3通りしかないので、うち少ない2種を総当たりしよう。
内側のループで余計な判定等を減らし、定数倍最適化すればO(N^2)が通る。

int N,M;
vector<int> C[4];
vector<ll> S[4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		C[x].push_back(y);
	}
	for(i=1;i<=3;i++) {
		sort(ALL(C[i]));
		reverse(ALL(C[i]));
		S[i].push_back(0);
		FORR(c,C[i]) S[i].push_back(S[i].back()+c);
	}
	
	int a=1,b=2,c=3;
	if(C[a].size()>C[b].size()) swap(a,b);
	if(C[b].size()>C[c].size()) swap(b,c);
	if(C[a].size()>C[b].size()) swap(a,b);
	
	S[c].clear();
	FOR(i,300005) S[c].push_back(-1LL<<60);
	S[c].push_back(0);
	FOR(i,C[c].size()) {
		FOR(x,c-1) S[c].push_back(S[c].back());
		S[c].push_back(S[c].back()+C[c][i]);
	}
	while(S[c].size()<=M+300005) S[c].push_back(S[c].back());
	
	ll ret=0;
	int as=C[a].size(), bs=C[b].size();
	for(i=0;i<=as;i++) {
		int w=M-i*a+300005;
		for(j=0;j<=bs;j++) {
			ret=max(ret,S[a][i]+S[b][j]+S[c][w]);
			w-=b;
		}
	}
	
	cout<<ret<<endl;
}

まとめ

Codeforcesは32bit環境なのかな。64bit演算が妙に遅い。