883E - Field of Wonders

1500
  • Quiz
  • AC
  • 問題意図
    • ＊で隠された文字列sがある
    • a～zの文字のうち、宣言したら確実に＊のいずれかが開く文字の個数を求めよ
  • 解説
    • editorialがないので書いておく
    • 答えの候補wordがM個与えられるが、すでに候補になりえないものは除外しておく
    • そして残った本当の候補たちについて、各文字cを宣言した時に候補全てが反応するならcは言うべき文字
    • 詳しくはコメント多めのコードを参照ください
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    string s;cin>>s;

    // すでに宣言された文字
    set<char> already;
    for(char c : s){
      if(c!='*')already.insert(c);
    }
    debug(already);

    // まだ宣言されていない文字
    set<char> candidate;
    rep(i,26){
      char c = 'a'+i;
      if(already.count(c))continue;
      candidate.insert(c);
    }
    debug(candidate);

    // 候補word
    ll M;cin>>M;
    VS S; // answer candiates
    rep(i,M){
      string t;cin>>t;
      bool take=true;
      rep(j,N){
        if(s[j]!='*')continue;
        // *の位置なのに、宣言済みの文字を使っているwordは答えの候補に入らない
        if(already.count(t[j]))take=false;
      }
      // *じゃない位置でs, tの文字が合っていないのも除外
      rep(j,N){
        if(s[j]!='*' && s[j]!=t[j])take=false;
      }
      if(take)S.push_back(t);
    }
    debug(S);
    ll sz=SZ(S);

    ll ans=0;
    for(char c : candidate){
      // cと言ったらどうなる？
      VI F(sz); // 反応したら1
      rep(j,N){
        if(s[j]!='*')continue;
        rep(k, sz){
          string t = S[k];
          if(t[j]==c)F[k]=1;
        }
      }
      // cと宣言して、候補文字列の全てが反応したなら、その文字は言うべき文字
      if(SUM(F)==sz)ans++;
    }
    p(ans);

    return 0;
}