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; } };