Acronyms [CSAcademy #54]

https://csacademy.com/contest/round-54/task/acronyms/

N個の文字列がある。
この文字列のうち、Acronymsな文字列が何個あるか数えよ。
Acronymsな文字列とは、その文字列を抜かしたN-1個の文字列の任意の順列(N-1個全て使わなくてもいい)の先頭だけを集めると、その文字列にすることができる文字列。
N≦10^5

解説

N個の文字列全てに対してAcronymsかどうか判定する。
まず、N-1個の文字列の先頭の文字の個数をカウントする(cnt配列)。
次に、i番目の文字列の全ての文字の個数をカウントする(cn配列)。
もし、全ての文字に対してcn[c]≦cnt[c]を満たせばその文字列はAcronymsである。
cnt配列の計算は毎回やるとTLEするので、最初に全てやって、毎回最初に消して、最後に戻す処理をすることで回避する。

int N;
string S[101010];
int cnt[30];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, N) cnt[S[i][0] - 'a']++;

    int ans = 0;
    rep(i, 0, N) {
        cnt[S[i][0] - 'a']--;

        vector<int> cn(26, 0);
        fore(c, S[i]) cn[c - 'a']++;
        
        int ok = 1;
        rep(j, 0, 26) if (cnt[j] < cn[j]) ok = 0;
        if (ok) ans++;

        cnt[S[i][0] - 'a']++;
    }
    cout << ans << endl;
}