TopCoder SRM 572 Div1 Meidum EllysBulls

TopCoder

問題

一人がn桁の数字を思い浮かべ、もう一人がその数字を当てるゲームをする。
（leading zeroがあってもよい）
当てるほうは、n桁の数字をm個言う。
それぞれに対して、自分の数字と言われた数字で、一致している桁数を答える。


言った数字と、そのときに答えられた数が与えられるとき、
元の数が一意に定まるならその数を、
複数個候補があるならAmbiguityを、
候補が一つもないならLiarを返せ。

制約条件

n≦9
m≦50

方針

半分全列挙。
数字の前半を列挙する。前半部分で一致する個数から、
後半部分で一致しなければならないvectorが作れる。これをmapなどにいれておく。


数字の後半部分も列挙する。
後半部分の一致する数のvectorを作り、最初に作ったmapから引く。
すると計算量O(10^n/2 * n^2 * m)くらいで答えが求まる。


探索でも出来るらしい。

ソースコード

class EllysBulls {
	public:
	string getNumber(vector <string> guesses, vector <int> bulls) {
		int n = guesses[0].size();
		int m = guesses.size();
		int ten[20] = {};
		string ans;
		map<vi, int> memo;
		map<vi, string> memo2;
		char buf[100], fmt[100], fmt2[100];
		sprintf(fmt, "%%0%dd", n / 2);
		sprintf(fmt2, "%%0%dd", n - n / 2);
		
		ten[0] = 1;
		rep(i, 19) ten[i + 1] = ten[i] * 10;
		rep(k, ten[n / 2]){
			sprintf(buf, fmt, k);
			vi hit = bulls;
			rep(i, m) rep(j, n / 2) if(guesses[i][j] == buf[j]) hit[i]--;
			memo[hit]++;
			memo2[hit] = buf;
		}
		int nn = n - n / 2;
		rep(k, ten[nn]){
			sprintf(buf, fmt2, k);
			vi hit(m);
			rep(i, m) for(int j = n / 2; j < n; j++) if(guesses[i][j] == buf[j - n / 2]) hit[i]++;
			if(memo[hit] > 1) return "Ambiguity";
			if(memo[hit] == 1){
				if(!ans.empty()) return "Ambiguity";
				ans = memo2[hit] + buf;
			}
		}
		return ans.empty() ? "Liar" : ans;
	}
};

追記

探索のコード。
hitが多いやつから、当たっている桁を決め付ける。
hitが全て0になったらその時点で探索は終了できる。


当たっている桁が1ずつ減っていくときおそらく計算量が最悪で、
9!回分岐があることになるが、なんか速い。
最悪ケース600msくらい。
2〜3個あるだけで、他はほぼ1msくらいで終わる。

int n, m;
string ans;
vector<string> g;
void rec(int num, string &s, vi &b, ll use){
	if(ans[0] == 'A') return;
	if(num == (1 << n) - 1){
		rep(i, m) if(b[i]) return;
		if(ans.empty()) ans = s;
		else ans = "Ambiguity";
		return;
	}
	int mx = 0, mxi = 0;
	rep(i, m) if(!(use >> i & 1) && b[i] > mx){
		mx = b[i];
		mxi = i;
	}
	if(mx == 0){
		//hitが全部0だったら、もう再帰しなくてよい。
		//まだ決まってない桁を消去法で決めるしかない。
		string ss = s;
		bool amb = 0;
		rep(i, n) if(!(num & 1 << i)){
			int f = 0;
			rep(j, m) f |= 1 << g[j][i] - '0';
			int pc = __builtin_popcount(f);
			if(pc > 9) return;
			if(pc < 9) amb = 1;
			rep(j, 10) if(!(f & 1 << j)) ss[i] = '0' + j;
		}
		if(!amb && ans.empty()) ans = ss;
		else ans = "Ambiguity";
		return;
	}
	int comb = (1 << mx) - 1;
	//大きさmxの部分集合を列挙
	while(comb < 1 << n){
		int c1 = comb & -comb, c2 = comb + c1;
		string ss = s;
		vi bb = b;
		//すでに見た桁とかぶっている場合は失敗。
		//bはまだみてない桁のうち、当たっているものの個数なので。
		if(num & comb) goto FAIL;

		//他のbを減らす。0未満になってたら失敗。
		rep(i, n) if(!(num & 1 << i) && (comb & 1 << i)){
			int d = g[mxi][i] - '0';
			rep(j, m) if(g[j][i] - '0' == d){
				if(--bb[j] < 0) goto FAIL;
			}
			ss[i] = d + '0';
		}
		rec(num | comb, ss, bb, use | 1ll << mxi);
		if(ans[0] == 'A') return;
		FAIL:;
		comb = ((comb & ~c2) / c1 >> 1) | c2;
	}
}

class EllysBulls {
	public:
	string getNumber(vector <string> guesses, vector <int> bulls) {
		g = guesses;
		n = g[0].size();
		m = g.size();
		ans = "";
		
		string s(n, '.');
		rec(0, s, bulls, 0);
		return ans.empty() ? "Liar" : ans;
	}
};

追記2

フォーマット指定子のパラメータ自体に変数を使いたいとき、
つまり%04dみたいなの4の部分とかを変数で指定したとき、
sprintf(buf, %0*d, width, num);みたいな書き方ができるらしい。
https://twitter.com/k_hanazuki/status/309330515100573696