AtCoder ARC #219 : A - Similarity

出だしはいいけど後半がダメダメ。
https://atcoder.jp/contests/arc219/tasks/arc219_a

問題

N個のM文字であるバイナリ文字列S[i]が与えられる。

M文字のバイナリ文字列Tのうち、各S[i]と最低１か所は一致するようなものがあればそれを構築せよ。

解法

DFSでTの1文字目から0/1どちらにするかを決めていく。
その際、まだTと一致する部分のないS[i]の添え字iの集合を状態として持っていこう。
途中添え字の集合が空になったら、その時点のTを答えればよい。

高々O(NM)回DFSする間には、添え字が空になる。

int N,M;
string S[20202];

void dfs(string& V,vector<int> A) {
	if(A.empty()) {
		while(V.size()<M) V+="0";
		cout<<"Yes"<<endl;
		cout<<V<<endl;
		exit(0);
		return;
	}
	int L=V.size();
	if(L==M) return;
	
	vector<int> B[2];
	FORR(a,A) B[S[a][L]-'0'].push_back(a);
	V+="1";
	dfs(V,B[0]);
	V.pop_back();
	V+="0";
	dfs(V,B[1]);
	V.pop_back();
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<int> A;
	FOR(i,N) {
		cin>>S[i];
		A.push_back(i);
	}
	string V;
	
	
	dfs(V,A);
	cout<<"No"<<endl;
}

まとめ

これはまぁすんなり。