TCO12 Round1C 250 PasswordXGuessing

2012-04-15

09:06 |

パスワードが決まってる（けど与えられない）。文字列がいくつか与えられて、各１文字を除いてそのパスワードと一致している。可能なパスワードが何通りあるか。

なにこれ難しいと焦る
各桁の数字の候補を桁x10の配列で管理
最初の文字列について、間違ってる文字の位置を仮定する
間違ってるとこはその文字以外残るし、あってるとこはその文字だけ残る
残りの文字列について、候補に含まれていることを確認する。だめなら仮定した桁はだめなので次。
その際、最初に仮定したとこ以外は正しいか間違ってるかわかるので優先して処理
その結果その文字列に関して間違ってる桁数によって決まってないとこが間違ってるかどうか決まるので間違ってたら候補を消す
各桁の候補数を掛けて各仮定について和をとってのが答え

あとで他人のを見て、候補とか考えないで間違ってる桁を 9 通り試せばいいだけと分かった。
パスワードを仮定すれば残りの文字列で間違ってる桁がちゃんと１コかどうかを確かめて OK なら ans++ するだけでしたちゃんちゃん
long long はひっかけ

class PasswordXGuessing {
	public:
	long long howMany(vector <string> G) {
		int N=G.size();
		int X=G[0].size();
		ll ans=0;
		//cout<<endl;
		REP(wr, X) {
			VI can(X*10, 1);
			REP(j, X) {
				if(j==wr) {
					can[j*10+G[0][j]-'0']=0;
				} else {
					REP(z, 10) if(z!=G[0][j]-'0') can[j*10+z]=0;
				}
			}
			//cout<<can<<endl;
			int ok=1;
			for(int i=1;i<N;i++) {
				//cout<<i<<endl;
				int x=0;
				VI w(X);
				REP(j, X) {
					if(can[j*10+G[i][j]-'0']) {
						if(j!=wr) w[j]=1;
					} else {
						x++;
						w[j]=1;
					}
				}
				//cout<<i<<endl;
				if(x>1) {ok=0;break;}
				if(x==1) {
					REP(j, X) if(w[j]==0) REP(zz, 10) if(zz!=G[i][j]-'0') can[j*10+zz]=0;
				}
				if(x==0) {
					REP(j, X) if(w[j]==0) can[j*10+G[i][j]-'0']=0;
				}
				if(!ok) break;
			}
			if(!ok) continue;
			ll lans=1;
			REP(j, X) {
				ll a=0;
				REP(z, 10) a+=can[j*10+z];
				lans *= a;
			}
			//cout<<can<<endl;
			//cout<<"+ "<<lans<<endl;
			ans += lans;
		}
		return ans;
	}
};