Codeforces #588 Div1 A. Marcin and Training Camp

いまいちだった回。
https://codeforces.com/contest/1229/problem/A

問題

N人の生徒がおり、パラメータA[i]と能力値B[i]が与えられる。
ここから2名以上のサブセットを作り、その能力値の総和を最大化したい。
ただし、以下の状態が生じないようにせよ。

• 人xがyより優れるとは、A[x]で立っているのに、A[y]で立っていない位置のbitが1個でもある。
• サブセット内で、ある人1人がほかの全員に優れる、ということが発生しない

解法

後者に反しない人はどんどん追加するのが良い。
同じパラメータの人が2名以上いたら、彼らは互いに後者の条件を発生させないので、問答無用で加える。
そうでない場合、自分のパラメータを内包する人がいたら加える。

int N;
ll A[7070],B[7070];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<ll,int> M;
	FOR(i,N) {
		cin>>A[i];
		M[A[i]]++;
	}
	FOR(i,N) cin>>B[i];
	
	vector<ll> C;
	FORR(m,M) if(m.second>1) C.push_back(m.first);
	ll ret=0;
	FOR(i,N) {
		int ok=0;
		FORR(c,C) if((~c&A[i])==0) ok=1;
		if(ok) ret+=B[i];
	}
	cout<<ret<<endl;
	
	
}

まとめ

問題文を読み解くのにちょっと手間取る。