2012 TCO Algorithm Round 1C Easy - PasswordXGuessing (×○)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11867&rd=15092

・数字で表わされるあるパスワードがある。
・そのパスワードを忘れてしまったが、複数の人がどのパスワードであったか答えてくれる。
・ただし、そのパスワードは思い出したものであるため1文字だけ間違っている。
・このとき、元のパスワードとして考えられるものの数を求める。

解き方


・dpを利用する?
・各桁についてあっているか、間違っているか、どちらでもよいかの情報をもつ
・でもこれだと計算量が間に合わない・・・

→他の人のコードをみる

・パスワードは50ケタであるので、最悪50*10=500個しか存在しない
・よって全探索可能

・反省:全探索の検討が足りなかった。ぱっとdp?と思ってしまったが解の候補、探索の候補どちらも全探索を検討するのが基本。

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class PasswordXGuessing {

public: long long howMany(vector<string> guesses) {
int n=guesses.size(),m=guesses[0].size();

set<string> s;
FORE(i,0,n){
set<string> tmp;
FORE(j,0,m)for(char ch='0';ch<='9';ch++)if(ch!=guesses[i][j]){
string str=guesses[i];
str[j]=ch;
if(i==0 || s.find(str)!=s.end())tmp.insert(str);
}
s=tmp;
}
return s.size();
}

};
このエントリーをはてなブックマークに追加