TopCoder SRM 596 Div1 Medium BitwiseAnd

さてMedium。Easyをさっさと解いたおかげでかなり時間があった。
なんとか本番提出できたと思ったら、またもしょうもないミスでWA。
http://community.topcoder.com/stat?c=problem_statement&pm=12792

問題

N要素の数列を考える。どの２要素のandを取っても0ではなく、どの３要素のandをとっても0になるようにしたい。
N要素のうち一部Sが指定されているとき、上記条件を満たすよう残りの要素を埋め、辞書順で最初に来る者を答えよ。

解法

N要素の各bitを見たとき、同じbit位置が1となる要素は高々2でなければならない。
3以上あると、そのbitが1になる要素のandは0ではなくなってしまい、条件を満たさない。
よってまず各bitが使用されている数を求めておく。

NからSの要素数を除いた残りL要素を求めていく。
L要素のそれぞれはSの各要素とandをとって0でないようにしなければならない。
よって、そのためにL要素の値を以下のように選んでいく。

• Sの各要素の各bitのうち、そのbitの使用数が全体で1である最小値を求め、Lの要素に加算する。もちろんこの際bitの使用数は増加する。
• Sの全要素に対し上記のようなbitを取れない場合、答えはない。

次に、L要素内のandはまだ0にしかならない状態である。
よって、まだ未使用なbitを探し、L要素中の２要素に割り当てていけばよい。

class BitwiseAnd {
	public:
	int M,L;
	
	vector<long long> lexSmallest(vector<long long> S, int N) {
		int b[61],c[61],aa[61];
		int i,j,x,y,z;
		sort(S.begin(),S.end());
		M=S.size();
		L=N-M;
		ZERO(aa);
		ZERO(b);
		
		FOR(j,60) FOR(i,M) if(S[i] & (1LL<<j)) b[j]++,aa[j]=i;
		
		FOR(x,M) for(y=x+1;y<M;y++) if((S[x] & S[y])==0) return vector<long long>();
		FOR(x,M) for(y=x+1;y<M;y++) for(z=y+1;z<M;z++) {
			if((S[x] & S[y] & S[z])!=0) return vector<long long>();
		}
		
		if(L==0) return S;
		
		vector<ll> S2;
		FOR(i,L) {
			ll t=0;
			ll ma=0;
			FOR(j,60) {
				if(b[j]!=1) continue;
				if((ma & (1LL<<aa[j]))==0) {
					ma |= 1LL<<aa[j];
					t |= 1LL<<j;
					b[j]++;
				}
			}
			if(ma != (1LL<<M)-1) return vector<long long>();
			
			S2.push_back(t);
		}
		
		FOR(i,60) {
			if(b[i]!=0) continue;
			FOR(x,L) for(y=x+1;y<L;y++) {
				if((S2[x] & S2[y])==0) {
					S2[x] |= 1LL<<i;
					S2[y] |= 1LL<<i;
					goto out;
				}
			}
			out:
			;
		}
		
		FOR(x,L) for(y=x+1;y<L;y++) if((S2[x] & S2[y])==0) return vector<long long>();
		FOR(i,L) S.push_back(S2[i]);
		sort(S.begin(),S.end());
		return S;
	}
};

まとめ

これ解ければ久々の２ケタ順位だったのにな。