kmjp's blog

競技プログラミング参加記です

Lyft Level 5 Challenge 2018 - Elimination Round : F. Boolean Computer

これは方針があっていたので本番Eを無視して取り組むべきだった…。
http://codeforces.com/contest/1033/problem/F

問題

W bit以下の値からなるN個の整数集合A[i]が与えられる。
2値の関数f(x,y)は、次のように定義される。

  • x,yをそれぞれW個のbool値とみなしたとき、それぞれのbitでand, or, xor, nand, nor, not xorのどれを取るかが与えられる。

M個のクエリが与えられる。
各クエリでは、fにおけるW個のbool値の演算方法で構成される。
f(A[i],A[j])=0となるi,jの対がいくつであるか求めよ。

解法

各iに対し、f(A[i], y)=0となるyを列挙したい。
A[i]とW個の演算子が決まったとき、yのW個のbitにおいて

  • 0でも1でも演算後0になる
  • 1なら演算後0になる
  • 0なら演算後0になる
  • 0でも1でも演算後0にならない

の4通りである。
よって、先に前処理として各bitがこの4通りのいずれかである場合、条件を満たすA[y]がいくつあるか求めておこう。
これは高速ゼータ変換の要領でO(W*4^W)で済ませることができる。

あとはA[i]を総当たりしつつ、yの各bitが上記4通りのどれであるかを求めて、前処理テーブルを用いて該当するyが何個あるか足しこんで行こう。

int W,N,M;
int A[1<<12];

int num[1<<24];
int table[256][2];

int hoge(int v,char c) {
	if(c=='A') return (v==1)?1:3;
	if(c=='O') return (v==1)?0:1;
	if(c=='X') return (v==1)?2:1;
	if(c=='a') return (v==1)?2:0;
	if(c=='o') return (v==1)?3:2;
	if(c=='x') return (v==1)?1:2;
	return 0;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>N>>M;
	FOR(i,N) cin>>x, A[x]++;
	FOR(i,1<<W) {
		int pos=0;
		FOR(j,W) {
			pos<<=2;
			if(i&(1<<(W-1-j))) pos|=2;
			else pos|=1;
		}
		num[pos]=A[i];
	}
	FOR(i,2*W) {
		FOR(j,1<<(2*W)) if(j&(1<<i)) num[j]+=num[j^(1<<i)];
	}
	FOR(i,256) {
		table[i][0]=hoge(0,i);
		table[i][1]=hoge(1,i);
	}
	
	while(M--) {
		cin>>s;
		ll ret=0;
		FOR(j,1<<W) {
			int pat=0;
			FOR(i,W) {
				pat<<=2;
				if(table[s[i]][(j>>(W-1-i))&1]==0) break;
				pat |= table[s[i]][(j>>(W-1-i))&1];
			}
			ret+=A[j]*num[pat];
		}
		cout<<ret<<endl;
	}
	
}

まとめ

完全に解く順番の戦略ミスでもったいない。