Shockers [Codeforces Round #454 A]

http://codeforces.com/contest/906/problem/A

文字当てゲームをする。
相手は'a'～'z'の1つを決める。
これに対して自分はN回行動した。

• 行動"! s" := 文字列sを渡すと、その中に決められた文字が含まれていたので、攻撃される
• 行動". s" ;= 文字列sを渡すと、その中に決められた文字が含まれていなかったので、何もされない
• 行動"? c" := 文字cが答えだろうと聞いた。最後のN回目は必ず正解であるが、それ以外は不正解で、不正解なら攻撃される

自分は行動の最中に答えが分かっているにも関わらず攻撃されている可能性がある。
答えがもう出せるのに無駄に攻撃された回数は？

解法

http://codeforces.com/contest/906/submission/33572682

su配列を用意する。
「su[c] := 文字cが答えかどうか疑わしい」
これを更新していき、su配列でtrueとなる要素の数が1つになれば特定したことになるので、その場合にendフラグを1にする。
もしendがtrueならば、それ以降の行動で". s"以外は攻撃されるので、その個数を数える（最後は正解するので数えない）
　
問題は行動によってsu配列がどう変わるかである。
行動"! s"では文字列sに含まれる文字以外の文字は候補から外れることが分かる。
そのため、含まれない文字列のsuを0にする。
行動". s"では文字列sに含まれる文字は候補から外れることが分かる。
そのため、含まれる文字列のsuを0にする。
行動"? c"では最後以外は必ず不正解なのでsu[c]=0とする
毎行動の後にsuで1が立っている個数を数えて、endフラグを更新していく。

int N;
string T[101010], S[101010];
int su[26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> T[i] >> S[i];

    rep(i, 0, 26) su[i] = 1;
    int end = 0, ans = 0;
    rep(i, 0, N - 1) {
        if (end) {
            if (T[i] != ".") ans++;
            continue;
        }

        if (T[i] == "!") {
            vector<int> f(26, 1);
            fore(c, S[i]) f[c - 'a'] = 0;
            rep(i, 0, 26) if (f[i]) su[i] = 0;
        }
        else if (T[i] == ".") {
            fore(c, S[i]) su[c - 'a'] = 0;
        }
        else {
            su[S[i][0] - 'a'] = 0;
        }

        int c = 0;
        rep(i, 0, 26) if (su[i]) c++;
        if (c == 1) end = 1;
    }
    cout << ans << endl;
}