TCO12 R1C 250pt : PasswordXGuessing

問題概要

ある数字列X(Xの長さは50以下)がある。いくつかの適当Xを一文字だけ置換した数字列が与えられるので、Xとして考えられるものがいくつあるか求める問題。

解法

候補はたかだか10*50しかないので全生成してチェックすれば良い。

acceptされたコード

#include <vector>
#include <string>
#include <set>
using namespace std;

struct PasswordXGuessing {

	long long howMany(vector <string> guesses) {
		const int N = guesses.size();
		vector< set<string> > cands(N);
		for(int i=0; i<N; ++i){
			for(int j=0; j<(int)guesses[i].length(); ++j){
				for(char d='0'; d<='9'; ++d)if(d != guesses[i][j]){
					string cur = guesses[i];
					cur[j] = d;
					cands[i].insert(cur);
				}
			}
		}

		int ans = 0;
		for(set<string>::iterator itr = cands[0].begin(); itr != cands[0].end(); ++itr){
			bool ok = true;
			for(int i=1; i<N; ++i){
				ok &= (cands[i].find(*itr) != cands[i].end());
			}
			if(ok){
				++ans;
			}
		}

		return ans;
	}

};