AOJ 0322 Slates

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0322

解法

二分探索で解ける．
左が欠けているやつを考えるときは末尾から比べたいので，各文字を反転した文字列集合も別に持っておく．
与えられた石版に ? がある場合は26文字全通り試す．
左が欠けている場合，反転した文字列集合にたいして，石版の文字の末尾をインクリメントした文字の lower_bound と，石版の文字の lower_bound の差がその時の答え．
右が欠けている場合は同じことを反転してないほうの文字列集合にたいしてやる．

たとえば apple, apricot が集合に合って，ap* を調べたい場合，"aq" による lower_bound と "ap" による lower_bound を取ると apple, apricot 分の幅が得られる．

計算量は O(NlogN + M|S|logN)．（|S| は石版の文字列長）

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> ws(n);
    set<string> origin;
    for(int i = 0; i < n; ++i) {
        cin >> ws[i];
        origin.insert(ws[i]);
    }
    auto rws = ws;
    for(auto& s : rws) reverse(begin(s), end(s));
    sort(begin(ws), end(ws));
    sort(begin(rws), end(rws));

    while(m--) {
        string ss;
        cin >> ss;
        bool left = ss[0] == '*', right = ss.back() == '*';
        string s;
        for(auto c : ss) {
            if(c != '*') s += c;
        }

        ll ans = 0;
        auto get_cnt = [](vector<string> const& ws, string& s) {
            auto l = lower_bound(begin(ws), end(ws), s);
            s.back() += 1;
            auto r = lower_bound(begin(ws), end(ws), s);
            s.back() -= 1;
            return r - l;
        };
        if(left) {
            reverse(begin(s), end(s));
            ans += get_cnt(rws, s);
        } else if(right) {
            ans += get_cnt(ws, s);
        } else {
            ans += origin.count(s);
        }

        for(int i = 0; i < (int)s.size(); ++i) {
            if(s[i] == '?') {
                for(char c = 'a'; c <= 'z'; ++c) {
                    s[i] = c;
                    if(left) {
                        ans += get_cnt(rws, s);
                    } else if(right) {
                        ans += get_cnt(ws, s);
                    } else {
                        ans += origin.count(s);
                    }
                }
                break;
            }
        }

        cout << ans << endl;
    }
}

感想

最初これにロリハ持ち出して解こうとして最悪だった．挙げ句MLEするし……．うーん……．