kojingharangの日記

SRM 572 Div1 500 EllysBulls

08:45 |

• ある K 桁の数字を N 回当てるゲームをする。推測した K 桁の数字 G[i] と、それに対して当たった桁の個数 B[i] が与えられる。
• 正解の数字が存在しないなら "Liar", 1 通りに定まるならそれを, 2 通り以上あるなら "Ambiguity" を返すという問題。
• 1≦N≦50, 2≦K≦9

• 10**9 通りは試せない
• だめそうだよなぁと思いつつも、有りうる候補を管理して明らかにだめなやつを消していく作戦
• いろいろ書いてうまくいかないうちに終了。

• あとで

• 半分全列挙らしい
• 前半 K/2 桁に対して各推測が何個一致するかを求める。残り何個一致しなきゃいけないかわかるのでそれを map に記録
• 後半 K-K/2 桁に対して同様のことをやって map を引いて、あったら答えを構築
• 後半に対して前半が 2 個以上あったり、すでに構築されてたりするときは Ambiguity

• なんかいろいろ出力しすぎ

• ↓あとで(accepted in practice room)

class EllysBulls {
	public:
	string getNumber(vector <string> G, vector <int> B) {
		int N=G.size(), K=G[0].size();
		map<VI, PII> rests;
		int K0=K/2, K1=K-K0;
		VI ten(1, 1);
		REP(i, 6) ten.PB(ten.back()*10);
		cout<<ten<<endl;
		cout<<K0<<" "<<K1<<endl;
		//return "";
		REP(v, ten[K0]) {
			//cout<<"p1 "<<v<<endl;
			char buf[20];
			sprintf(buf, "%0*d", K0, v);
			//cout<<"buf: "<<string(buf)<<endl;
			VI rest(N);
			int ok=1;
			REP(gi, N) {
				int match=0;
				REP(k, K0) match += buf[k]==G[gi][k];
				if(B[gi]-match<0) {ok=0;break;}
				rest[gi] = B[gi]-match;
			}
			if(ok) {
				rests[rest].first++;
				rests[rest].second = v;
			}
		}
		//cout<<rests<<endl;
		string ans;
		REP(v, ten[K1]) {
			char buf[20];
			sprintf(buf, "%0*d", K1, v);
			VI key(N);
			REP(gi, N) {
				int match=0;
				REP(k, K1) match += buf[k]==G[gi][K0+k];
				key[gi] = match;
			}
			//cout<<"key: "<<key<<endl;
			if(rests.count(key)) {
				//cout<<"p2 count "<<v<<" "<<rests.count(key)<<endl;
				if(rests[key].first > 1) return "Ambiguity";
				if(ans.size()) return "Ambiguity";
				char buf[30];
				sprintf(buf, "%0*d", K0, rests[key].second);
				sprintf(&buf[K0], "%0*d", K1, v);
				ans = string(buf);
			}
		}
		if(ans.size()==0) return "Liar";
		return ans;
	}
};

ツイートする