Coder-Strike 2014 Round1 - C. Pattern

Coder-Strike Round1に参加。
Dで苦戦したけど2Hackを決めそこそこの順位。
http://codeforces.com/contest/412/problem/C

問題

N個の同じ長さの文字列が与えられる。
各文字はアルファベット小文字かワイルドカードを示す'?'である。

これらの全文字とマッチできる文字列のうち、ワイルドカード数が最小のものを示せ。

解法

答えの文字列の各位置に対し、以下の処理を行えばよい。

• ２種類以上の小文字が登場するなら、そこは'?'にする。
• １種類の小文字が登場するなら、そこはその文字にする。
• ０種類の小文字、すなわち全部'?'なら、適当な小文字を割り当てる。

int N;
int mask[100001];
char hoge[100001];
void solve() {
	int f,i,j,k,l,x,y;
	string S;
	cin>>N;
	FOR(i,N) {
		cin>>S;
		l=S.size();
		FOR(x,S.size()) {
			if(S[x]=='?') mask[x] |= 1<<30;
			else mask[x] |= 1<<(S[x]-'a');
		}
	}
	FOR(i,l) {
		x=__builtin_popcount(mask[i]&((1<<26)-1));
		if(x==0) hoge[i]='a';
		else if(x==1) {
			FOR(y,26) if(mask[i]&(1<<y)) hoge[i]='a'+y;
		}
		else hoge[i]='?';
	}
	_P("%s\n",hoge);
}

まとめ

Div2 Cとしてもちょっと簡単に感じた。