Codeforces #773 : Div1 D. Two Arrays

結構力技。
https://codeforces.com/contest/1641/problem/D

問題

N個のM要素からなる整数集合と、それぞれの重みWが与えられる。
集合の対のうち、それらの和集合の全要素が相異なるものがあれば、重みの和の最小値を求めよ。

解法

数列を重み順で昇順に並べ替える。
1つ目の数列を総当たりし、2つ目の数列の候補として有効なものをbitsetで管理する。

• 1つ目の数列と同じ要素を持つ数列は、bitsetのビットをクリアする。その際、登場頻度の多い数列に関してはあらかじめそのような数列の集合をbitsetで保持しておき、高速にクリアできるようにしておく。

あとは、bitsetの中で立っているbitのうち一番小さなインデックスのものが2つ目の数列の候補になる。

int N,M;
int A[101010][5];
ll W[101010];
vector<int> C[505050];
int AID[505050],BSID[505050];
bitset<100040> BS[1000],cur,tcur;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<int> V;
	vector<pair<int,int>> cand;
	FOR(i,N) {
		FOR(j,M) {
			cin>>A[i][j];
			V.push_back(A[i][j]);
		}
		cin>>W[i];
		cand.push_back({W[i],i});
		cur[i]=1;
	}
	sort(ALL(cand));
	FOR(i,N) AID[cand[i].second]=i;
	
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	FOR(i,N) {
		FOR(j,M) {
			A[i][j]=lower_bound(ALL(V),A[i][j])-V.begin();
			C[A[i][j]].push_back(i);
		}
	}
	ll ret=1LL<<60;
	x=0;
	FOR(i,V.size()) {
		if(C[i].size()<500) {
			BSID[i]=-1;
		}
		else {
			BSID[i]=x++;
			FOR(y,N) BS[BSID[i]][y]=1;
			FORR(c,C[i]) BS[BSID[i]][AID[c]]=0;
		}
	}
	
	FOR(i,N) {
		tcur=cur;
		FOR(j,M) {
			if(BSID[A[i][j]]==-1) {
				FORR(c,C[A[i][j]]) tcur[AID[c]]=0;
			}
			else {
				tcur&=BS[BSID[A[i][j]]];
			}
		}
		x=tcur._Find_first();
		if(x<N) ret=min(ret,W[i]+W[cand[x].second]);
	}
	
	if(ret==1LL<<60) ret=-1;
	cout<<ret<<endl;
}

まとめ

bitset解でもTLの半分以下で間に合うのか。