TopCoder SRM 572 Div1 Medium EllysBulls

本番凡ミスコードが残っていた上、それを取り除いても微妙にTLEした。
多分他にもTLEした人多かっただろうな。
http://community.topcoder.com/stat?c=problem_statement&pm=12420

問題

マスターマインド風のゲームを行う。
ある答えの数値がある。
ここで、同じ桁数の数字に対し答えの数値と一致する桁の数がわかっている。
答えの数値が１つに絞れるならそれを答える。
絞れないまたは１つもあり得ないなら、そう答える。

解答

各桁0～9の答えを仮定して、答えの桁数と矛盾しないかDFSしても良いが、数値が最大10^9なので途中適度に枝刈りしないとTLEする。
実際本番はこれでTLEした。

そこでその後の練習では、半列挙方式を採用した。
まず、先頭5桁の数値のうち、一致可能な桁数の制限に合うものを列挙し、一致した桁数をキーとした連想配列に入れる。
次に、残りの桁数の数値のうち、やはり一致可能な桁数の制限に合うものを列挙し、残り一致桁数をキーとした別の連想配列にいれる。
これらはそれぞれ10^5程度のループで完了する。

両者の連想配列を見て、両者同じキーの数値があればそれらの数値を連結して答えが得られる。
同じキーの数値がなければ、条件を満たせる数字はない。

class EllysBulls {
	public:
	int N,L;
	string res;
	map<string, vector<string> > FF,LL;
	vector<string> G;
	ll dig[10];
	
	string getNumber(vector <string> guesses, vector <int> bulls) {
		G=guesses;
		N=guesses.size();
		L=guesses[0].size();
		int i,x,y,z;
		char hoge[10];
		string res="Liar";
		
		dig[0]=1;
		FOR(i,9) dig[i+1]=dig[i]*10;
		ZERO(hoge);
		FF.clear();
		LL.clear();
		
		if(L<=5) {
			int num=-1;
			
			FOR(i,dig[L]) {
				FOR(x,L) hoge[x]='0'+(i/dig[x])%10;
				int ng=0;
				FOR(x,N) {
					z=bulls[x];
					FOR(y,L) if(G[x][y]==hoge[y]) z--;
					if(z!=0) ng++;
				}
				
				if(ng==0) {
					if(res!="Liar") return "Ambiguity";
					res=string(hoge);
				}
			}
		}
		else {
			//前半5ケタ
			char Bs[100];
			
			FOR(i,dig[5]) {
				FOR(x,5) hoge[x]='0'+(i/dig[x])%10;
				FOR(x,N) Bs[x]='0'+bulls[x];
				Bs[N]=0;
				
				int ng=0;
				FOR(x,N) {
					FOR(y,5) if(G[x][y]==hoge[y]) Bs[x]--;
					if(Bs[x]<'0') ng++;
				}
				
				if(ng==0) FF[string(Bs)].push_back(string(hoge));
			}
			
			//後半
			ZERO(hoge);
			FOR(i,dig[L-5]) {
				FOR(x,L-5) hoge[x]='0'+(i/dig[x])%10;
				FOR(x,N) Bs[x]='0';
				Bs[N]=0;
				
				int ng=0;
				FOR(x,N) {
					FOR(y,L-5) if(G[x][5+y]==hoge[y]) Bs[x]++;
					if(Bs[x]>bulls[x]+'0') ng++;
				}
				if(ng==0) LL[string(Bs)].push_back(string(hoge));
			}
			
			int num=0;
			for(map<string, vector<string> >::iterator mit=FF.begin();mit!=FF.end();mit++) {
				map<string, vector<string> >::iterator mit2=LL.find(mit->first);
				
				if(mit2==LL.end()) continue;
				num += mit->second.size() * mit2->second.size();
				if(num>=2) return "Ambiguity";
				res = mit->second[0] + mit2->second[0];
			}
		}
		
		return res;
		
	}

};

まとめ

半分ずつ列挙して後で合わせる考え方、もっとさらっと思い浮かべられるようになろう。